An approximation algorithm for the longest path problem in solid grid graphs

References

• N. Alon, R. Yuster, and U. Zwick, Color-coding, J. ACM (JACM) 42 (1995), pp. 844–856. doi: 10.1145/210332.210337
   Web of Science ®Google Scholar
• A. Asgharian Sardroud and A. Bagheri, An approximation algorithm for the longest cycle problem in solid grid graphs, Discrete Appl. Math. (2014), to appear. doi:10.1016/j.dam.2015.10.022.
   Web of Science ®Google Scholar
• N. Bansal, L.K. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko, Further improvements in competitive guarantees for qos buffering, Proceedings of the International Colloquium on Automata, Languages and Programming, Turku, Finland, Springer, 2004, pp. 196–207.
   Google Scholar
• A. Björklund and T. Husfeldt, Finding a path of superlogarithmic length, SIAM J. Comput. 32 (2003), pp. 1395–1402. doi: 10.1137/S0097539702416761
   Web of Science ®Google Scholar
• A. Björklund, T. Husfeldt, and S. Khanna, Approximating longest directed paths and cycles, Proceedings of the International Colloquium on Automata, Languages and Programming, Turku, Finland, Springer, 2004, pp. 222–233.
   Google Scholar
• R.W. Bulterman, F.W. van der Sommen, G. Zwaan, T. Verhoeff, A.J.M. van Gasteren, and W.H.J. Feijen, On computing a longest path in a tree, Inform. Process. Lett. 81 (2002), pp. 93–96. doi: 10.1016/S0020-0190(01)00198-3
   Web of Science ®Google Scholar
• R. Cerulli, R. De Leone, and G. Piacente, A modified auction algorithm for the shortest path problem, Optim. Methods Softw. 4 (1994), pp. 209–224. doi: 10.1080/10556789408805588
   Google Scholar
• G. Chen, Z. Gao, X. Yu, and W. Zang, Approximating longest cycles in graphs with bounded degrees, SIAM J. Comput. 36 (2006), pp. 635–656. doi: 10.1137/050633263
   Web of Science ®Google Scholar
• L. Di Puglia Pugliese and F. Guerriero, Dynamic programming approaches to solve the shortest path problem with forbidden paths, Optim. Methods Softw. 28 (2013), pp. 221–255. doi: 10.1080/10556788.2011.630077
   Web of Science ®Google Scholar
• T. Feder and R. Motwani, Finding large cycles in Hamiltonian graphs, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, Canada, 2005, pp. 166–175.
   Google Scholar
• H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (2007), pp. 1648–1671. doi: 10.1137/S0097539704445366
   Web of Science ®Google Scholar
• H.N. Gabow and S. Nie, Finding a long directed cycle, ACM Trans. Algorithms (TALG) 4 (2008), pp. 7:1–7:21.
   Google Scholar
• H.N. Gabow and S. Nie, Finding long paths, cycles and circuits, Proceedings of the 19th Annual International Symposium on Algorithms and Computation, Surfers Paradise, Gold Coast, Australia, Springer, 2008, pp. 752–763.
   Google Scholar
• F. Guerriero and L. Di Puglia Pugliese, Multi-dimensional labelling approaches to solve the linear fractional elementary shortest path problem with time windows, Optim. Methods Softw. 26 (2011), pp. 295–340. doi: 10.1080/10556780903483364
   Web of Science ®Google Scholar
• G. Gutin, Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math. 6 (1993), pp. 270–273. doi: 10.1137/0406020
   Web of Science ®Google Scholar
• K. Ioannidou, G.B. Mertzios, and S.D. Nikolopoulos, The longest path problem is polynomial on interval graphs, Proceedings of 34th International Symposium on Mathematical Foundations of Computer Science, Novy Smokovec, High Tatras, Slovakia, Springer, 2009, pp. 403–414.
   Google Scholar
• A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), pp. 676–686. doi: 10.1137/0211056
   Web of Science ®Google Scholar
• D. Karger, R. Motwani, and G.D.S. Ramkumar, On approximating the longest path in a graph, Algorithmica 18 (1997), pp. 82–98. doi: 10.1007/BF02523689
   Web of Science ®Google Scholar
• F. Kehsavarz Kohjerdi, A. Bagheri, and A. Asgharian Sardroud, A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math. 160 (2012), pp. 210–217. doi: 10.1016/j.dam.2011.08.010
   Web of Science ®Google Scholar
• G.B. Mertzios and D.G. Corneil, A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM J. Discrete Math. 26 (2012), pp. 940–963. doi: 10.1137/100793529
   Web of Science ®Google Scholar
• T. Nishizeki and M.S. Rahman, Planar Graph Drawing, Vol. 12, World Scientific Pub Co Inc, Singapore, 2004.
   Google Scholar
• J.R. Sack and J. Urrutia, Handbook of Computational Geometry, North-Holland Publishing Co., Amsterdam, 2000.
   Google Scholar
• R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, Proceedings of the 15th Annual International Symposium on Algorithms and Computation, Hong Kong, China, Springer, 2004, pp. 871–883.
   Google Scholar
• R. Uehara and Y. Uno, On computing longest paths in small graph classes, Internat. J. Found. Comput. Sci. 18 (2007), pp. 911–930. doi: 10.1142/S0129054107005054
   Web of Science ®Google Scholar
• C. Umans and W. Lenhart, Hamiltonian cycles in solid grid graphs, Proceedings of 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, USA, 1997, pp. 496–505.
   Google Scholar
• W. -Q. Zhang and Y. -J. Liu, Approximating the longest paths in grid graphs, Theoret. Comput. Sci. 412 (2011), pp. 5340–5350. doi: 10.1016/j.tcs.2011.06.010
   Web of Science ®Google Scholar