×

zbMATH — the first resource for mathematics

An approximation algorithm for the longest cycle problem in solid grid graphs. (English) Zbl 1333.05091
Summary: Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least \(\frac{2 n}{3} + 1\) in 2-connected \(n\)-node solid grid graphs.

MSC:
05C12 Distance in graphs
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alon, Noga; Yuster, Raphael; Zwick, Uri, Color-coding, J. ACM, 42, 4, 844-856, (1995) · Zbl 0885.68116
[2] Bansal, Nikhil; Fleischer, Lisa K.; Kimbrel, Tracy; Mahdian, Mohammad; Schieber, Baruch; Sviridenko, Maxim, Further improvements in competitive guarantees for QoS buffering, (Proceedings of the International Colloquium on Automata, Languages and Programming, (2004), Springer), 196-207 · Zbl 1098.68516
[3] Björklund, Andreas; Husfeldt, Thore, Finding a path of superlogarithmic length, SIAM J. Comput., 32, 6, 1395-1402, (2003) · Zbl 1041.68066
[4] Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev, Approximating longest directed paths and cycles, (Proceedings of the International Colloquium on Automata, Languages and Programming, (2004), Springer), 222-233 · Zbl 1098.68094
[5] Bulterman, R. W.; van der Sommen, F. W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A. J.M.; Feijen, W. H.J., On computing a longest path in a tree, Inform. Process. Lett., 81, 2, 93-96, (2002) · Zbl 1032.68671
[6] Chen, Guantao; Gao, Zhicheng; Yu, Xingxing; Zang, Wenan, Approximating longest cycles in graphs with bounded degrees, SIAM J. Comput., 36, 3, 635-656, (2006) · Zbl 1118.05047
[7] Feder, Tomás; Motwani, Rajeev, Finding large cycles in Hamiltonian graphs, (Proceedings of the 16th annual ACM-SIAM symposium on Discrete Algorithms, (2005), Society for Industrial and Applied Mathematics), 166-175 · Zbl 1297.05140
[8] Gabow, Harold N., Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput., 36, 6, 1648-1671, (2007) · Zbl 1135.68044
[9] Gabow, Harold N.; Nie, Shuxin, Finding a long directed cycle, ACM Trans. Algorithms, 4, 1, (2008), 7:1-7:21 · Zbl 1183.05078
[10] Gabow, Harold N.; Nie, Shuxin, Finding long paths, cycles and circuits, (Proceedings of the 19th annual International Symposium on Algorithms and Computation, (2008), Springer), 752-763 · Zbl 1183.05078
[11] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math., 6, 2, 270-273, (1993) · Zbl 0773.05071
[12] Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D., The longest path problem is polynomial on interval graphs, (Proceedings of 34th International Symposium on Mathematical Foundations of Computer Science, (2009), Springer), 403-414 · Zbl 1250.68128
[13] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[14] Karger, David; Motwani, Rajeev; Ramkumar, G. D.S., On approximating the longest path in a graph, Algorithmica, 18, 1, 82-98, (1997) · Zbl 0876.68083
[15] Kehsavarz Kohjerdi, F.; Bagheri, A.; Asgharian Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 3, 210-217, (2012) · Zbl 1237.05115
[16] Mertzios, George B.; Corneil, Derek G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM J. Discrete Math., 26, 3, 940-963, (2012) · Zbl 1256.05237
[17] Uehara, Ryuhei; Uno, Yushi, Efficient algorithms for the longest path problem, (Proceedings of the 15th annual International Symposium on Algorithms and Computation, (2004), Springer), 871-883 · Zbl 1116.05318
[18] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Internat. J. Found Comput. Sci., 18, 05, 911-930, (2007) · Zbl 1202.68291
[19] Umans, C.; Lenhart, W., Hamiltonian cycles in solid grid graphs, (Proceedings of 38th Annual Symposium on Foundations of Computer Science, (1997), IEEE), 496-505
[20] Zhang, W.; Liu, Y., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 39, 5340-5350, (2011) · Zbl 1222.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.