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 条
  • [11] On shortest disjoint paths in planar graphs
    Kobayashi, Yusuke
    Sommer, Christian
    DISCRETE OPTIMIZATION, 2010, 7 (04) : 234 - 245
  • [12] Parametric Shortest Paths in Planar Graphs
    Gajjar, Kshitij
    Radhakrishnan, Jaikumar
    2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, : 876 - 895
  • [13] On Shortest Disjoint Paths in Planar Graphs
    Kobayashi, Yusuke
    Sommer, Christian
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5878 : 293 - +
  • [14] Optimal pants decompositions and shortest homotopic cycles on an orientable surface
    De Verdiere, Eric Colin
    Lazarus, Francis
    JOURNAL OF THE ACM, 2007, 54 (04)
  • [15] On the shortest path problem with negative cost cycles
    Pugliese, Luigi Di Puglia
    Guerriero, Francesca
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2016, 63 (02) : 559 - 583
  • [16] Finding Alternative Shortest Paths in Spatial Networks
    Xie, Kexin
    Deng, Ke
    Shang, Shuo
    Zhou, Xiaofang
    Zheng, Kai
    ACM TRANSACTIONS ON DATABASE SYSTEMS, 2012, 37 (04):
  • [17] ON FINDING A CYCLE BASIS WITH A SHORTEST MAXIMAL CYCLE
    CHICKERING, DM
    GEIGER, D
    HECKERMAN, D
    INFORMATION PROCESSING LETTERS, 1995, 54 (01) : 55 - 58
  • [18] Finding the Shortest Path in Stochastic Graphs Using Learning Automata and Adaptive Stochastic Petri Nets
    Vahidipour, S. Mehdi
    Meybodi, Mohammad Reza
    Esnaashari, Mehdi
    INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS, 2017, 25 (03) : 427 - 455
  • [19] Shortest Path Tree Computation in Dynamic Graphs
    Chan, Edward P. F.
    Yang, Yaya
    IEEE TRANSACTIONS ON COMPUTERS, 2009, 58 (04) : 541 - 557
  • [20] A SHORTEST-PATH ALGORITHM FOR MANHATTAN GRAPHS
    KANCHANASUT, K
    INFORMATION PROCESSING LETTERS, 1994, 49 (01) : 21 - 25
12345