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 条

[41] A universal algorithm for finding the shortest distance between systems of points
Blatov, Igor A.
Kitaeva, Elena V.
Shevchenko, Alexander P.
Blatov, Vladislav A.
ACTA CRYSTALLOGRAPHICA A-FOUNDATION AND ADVANCES, 2019, 75 : 827 - 832
[42] REVERSE SHORTEST PATH PROBLEM FOR UNIT-DISK GRAPHS
Wang, Haitao
Zhao, Yiming
JOURNAL OF COMPUTATIONAL GEOMETRY, 2023, 14 (01) : 14 - 47
[43] Reverse Shortest Path Problem for Unit-Disk Graphs
Wang, Haitao
Zhao, Yiming
ALGORITHMS AND DATA STRUCTURES, WADS 2021, 2021, 12808 : 655 - 668
[44] Approximating Shortest Superstring Problem Using de Bruijn Graphs
Golovnev, Alexander
Kulikov, Alexander S.
Mihajlin, Ivan
COMBINATORIAL PATTERN MATCHING, 2013, 7922 : 120 - 129
[45] MAINTAINING SHORTEST PATHS UNDER DELETIONS IN WEIGHTED DIRECTED GRAPHS
Bernstein, Aaron
SIAM JOURNAL ON COMPUTING, 2016, 45 (02) : 548 - 574
[46] Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings
Cygan, Marek
Gabow, Harold N.
Sankowski, Piotr
JOURNAL OF THE ACM, 2015, 62 (04)
[47] All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time
Chan, Timothy M.
ACM TRANSACTIONS ON ALGORITHMS, 2012, 8 (04)
[48] Finding the k Shortest Paths for Co-Evolutionary Path Optimization
Hu, Xiao-Bing
Zhou, Jun
Li, Hang
Zhang, Ming-Kong
Liao, Jian-Qin
2018 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (IEEE SSCI), 2018, : 1906 - 1912
[49] Finding the Shortest Path in Stochastic Vehicle Routing: A Cardinality Minimization Approach
Cao, Zhiguang
Guo, Hongliang
Zhang, Jie
Niyato, Dusit
Fastenrath, Ulrich
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2016, 17 (06) : 1688 - 1702
[50] On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
Galbiati, G
INFORMATION PROCESSING LETTERS, 2003, 88 (04) : 155 - 159

← 1 2 3 4 5 →