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 条
  • [21] DYNAMIC ALGORITHMS FOR SHORTEST PATHS IN PLANAR GRAPHS
    FEUERSTEIN, E
    MARCHETTISPACCAMELA, A
    THEORETICAL COMPUTER SCIENCE, 1993, 116 (02) : 359 - 371
  • [22] Efficient Maintenance of Shortest Distances in Dynamic Graphs
    Greco, Sergio
    Molinaro, Cristian
    Pulice, Chiara
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2018, 30 (03) : 474 - 487
  • [23] Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time
    Lacki, Jakub
    Sankowski, Piotr
    ALGORITHMS - ESA 2011, 2011, 6942 : 155 - 166
  • [24] Efficient Solutions For Finding Vitality With Respect To Shortest Paths
    Kare, Anjeneya Swami
    Saxena, Sanjeev
    2013 SIXTH INTERNATIONAL CONFERENCE ON CONTEMPORARY COMPUTING (IC3), 2013, : 70 - 75
  • [25] Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs
    Roditty, Liam
    Zwick, Uri
    ACM TRANSACTIONS ON ALGORITHMS, 2012, 8 (04)
  • [26] To Meet or Not to Meet: Finding the Shortest Paths in Road Networks
    Huang, Weihuang
    Zhang, Yikai
    Shang, Zechao
    Yu, Jeffrey Xu
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2018, 30 (04) : 772 - 785
  • [27] An extension of labeling techniques for finding shortest path trees
    Ziliaskopoulos, Athanasios K.
    Mandanas, Fotios D.
    Mahmassani, Hani S.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 198 (01) : 63 - 72
  • [28] A Novel Shortest Path Approach for Multiple Layers of Graphs
    Lin, Zhiyuan
    Li, Yan
    2009 INTERNATIONAL SYMPOSIUM ON COMPUTER NETWORK AND MULTIMEDIA TECHNOLOGY (CNMT 2009), VOLUMES 1 AND 2, 2009, : 468 - 471
  • [29] Finding shortest paths on real road networks: the case for A*
    Zeng, W.
    Church, R. L.
    INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE, 2009, 23 (04) : 531 - 543
  • [30] Maximum Flows and Parametric Shortest Paths in Planar Graphs
    Erickson, Jeff
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, 135 : 794 - 804
12345