Longest (s, t)-paths in L-shaped grid graphs

被引：3
作者：
Keshavarz-Kohjerdi, Fatemeh [1 ]
Bagheri, Alireza [2 ]
机构：
[1] Shahed Univ, Dept Comp Sci, Tehran, Iran
[2] Amirkabir Univ Technol, Dept Comp Engn & IT, Tehran, Iran
来源：
OPTIMIZATION METHODS & SOFTWARE | 2019年 / 34卷 / 04期
关键词：
grid graph; Hamiltonian path; L-shaped grid graph; longest path; FINDING HAMILTONIAN (S; LINEAR-TIME ALGORITHM; PATHS; CYCLES;
D O I：
10.1080/10556788.2018.1460665
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L-shaped grid graph can be computed in linear time.
引用
收藏
页码：797 / 826
页数：30
相关论文
共 37 条
  • [1] Finding a path of superlogarithmic length
    Björklund, A
    Husfeldt, T
    [J]. SIAM JOURNAL ON COMPUTING, 2003, 32 (06) : 1395 - 1402
  • [2] On computing a longest path in a tree
    Bulterman, RW
    van den Sommen, FW
    Zwaan, G
    Verhoeff, T
    van Gasteren, AJM
    Feijen, WHJ
    [J]. INFORMATION PROCESSING LETTERS, 2002, 81 (02) : 93 - 96
  • [3] Chen SD, 2002, PARALLEL COMPUT, V28, P1293, DOI 10.1016/S0167-8191(02)00135-7
  • [4] Diestel R., 2000, GRAPH THEORY, DOI DOI 10.1007/978-3-662-53622-3
  • [5] Du L, 2010, EKSPLOAT NIEZAWODN, P17
  • [6] Felsner S., 2003, Journal of Graph Algorithms and Applications, V7, DOI 10.7155/jgaa.00075
  • [7] Gabow H.N., 2004, 36 ANN ACM S THEOR C, P407
  • [8] Gabow HN, 2008, LECT NOTES COMPUT SC, V5369, P752, DOI 10.1007/978-3-540-92182-0_66
  • [9] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
  • [10] Gorbenko A., 2012, LECT NOTES ELECT ENG, V107, P971, DOI DOI 10.1007/978-94-007-1839-5-105
1234