Finding Shortest Contractible and Shortest Separating Cycles in Embedded Graphs

被引：7
|
作者：
Cabello, Sergio [1 ]
机构：
[1] Univ Ljubljana, FMF, Dept Math, SI-1000 Ljubljana, Slovenia
来源：
ACM TRANSACTIONS ON ALGORITHMS | 2010年 / 6卷 / 02期
关键词：
Algorithms; Theory; 3-path condition; forbidden pairs; graphs on surfaces; topological graph theory; SURFACES;
D O I：
10.1145/1721837.1721840
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.
引用
收藏
页数：18
相关论文
共 50 条
  • [1] Finding shortest contractible and shortest separating cycles in embedded graphs
    Cabello, Sergio
    PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2009, : 616 - 624
  • [2] On packing shortest cycles in graphs
    Rautenbach, Dieter
    Regen, Friedrich
    INFORMATION PROCESSING LETTERS, 2009, 109 (14) : 816 - 821
  • [3] Finding Shortest Non-Trivial Cycles in Directed Graphs on Surfaces
    Cabello, Sergio
    de Verdiere, Eric Colin
    Lazarus, Francis
    PROCEEDINGS OF THE TWENTY-SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'10), 2010, : 156 - 165
  • [4] Shortest Non-trivial Cycles in Directed Surface Graphs
    Erickson, Jeff
    COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 236 - 243
  • [5] Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
    Lincoln, Andrea
    Williams, Virginia Vassilevska
    Williams, Ryan
    SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1236 - 1252
  • [6] MULTIPLE-SOURCE SHORTEST PATHS IN EMBEDDED GRAPHS
    Cabello, Sergio
    Chambers, Erin W.
    Erickson, Jeff
    SIAM JOURNAL ON COMPUTING, 2013, 42 (04) : 1542 - 1571
  • [7] Minimum Cuts and Shortest Homologous Cycles
    Chambers, Erin W.
    Erickson, Jeff
    Nayyeri, Amir
    PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, : 377 - 385
  • [8] Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers
    Erickson, Jeff
    Nayyeri, Amir
    PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2011, : 1166 - 1176
  • [9] Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
    Fox, Kyle
    PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 352 - 364
  • [10] FINDING CYCLES WITH TOPOLOGICAL PROPERTIES IN EMBEDDED GRAPHS
    Cabello, Sergio
    de Verdiere, Eric Colin
    Lazarus, Francis
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (04) : 1600 - 1614
12345