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 条

[31] Parallel Shortest-Path Queries in Planar Graphs
Aleksandrov, Lyudmil
Chapuis, Guillaume
Djidjev, Hristo
PROCEEDINGS OF THE ACM WORKSHOP ON HIGH PERFORMANCE GRAPH PROCESSING (HPGP'16), 2016, : 9 - 16
[32] Faster shortest paths in dense distance graphs, with applications
Mozes, Shay
Nussbaum, Yahav
Weimann, Oren
THEORETICAL COMPUTER SCIENCE, 2018, 711 : 11 - 35
[33] The Number of Shortest Paths in the (n, k)-Star Graphs
Cheng, Eddie
Qiu, Ke
Shen, Zhi Zhang
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT 1, 2010, 6508 : 222 - +
[34] An efficient oracle for counting shortest paths in planar graphs
Gong, Ye
Gu, Qian-Ping
THEORETICAL COMPUTER SCIENCE, 2022, 921 : 75 - 85
[35] Shortest node-disjoint paths on random graphs
De Bacco, C.
Franz, S.
Saad, D.
Yeung, C. H.
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2014,
[36] THE WEIGHTED REGION PROBLEM - FINDING SHORTEST PATHS THROUGH A WEIGHTED PLANAR SUBDIVISION
MITCHELL, JSB
PAPADIMITRIOU, CH
JOURNAL OF THE ACM, 1991, 38 (01) : 18 - 73
[37] Finding Shortest Vector Using Quantum NV Sieve on Grover
Kim, Hyunji
Jang, Kyoungbae
Oh, Yujin
Seok, Woojin
Lee, Wonhuck
Bae, Kwangil
Sohn, Ilkwon
Seo, Hwajeong
INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2023, PT I, 2024, 14561 : 97 - 118
[38] Finding Reliable Shortest Paths in Road Networks Under Uncertainty
Chen, Bi Yu
Lam, William H. K.
Sumalee, Agachai
Li, Qingquan
Shao, Hu
Fang, Zhixiang
NETWORKS & SPATIAL ECONOMICS, 2013, 13 (02) : 123 - 148
[39] Finding the Anti-block Vital Node of a Shortest Path
Nie, Zhe
Li, Yueping
2009 INTERNATIONAL CONFERENCE ON NEW TRENDS IN INFORMATION AND SERVICE SCIENCE (NISS 2009), VOLS 1 AND 2, 2009, : 680 - 684
[40] Finding shortest lattice vectors faster using quantum search
Laarhoven, Thijs
Mosca, Michele
van de Pol, Joop
DESIGNS CODES AND CRYPTOGRAPHY, 2015, 77 (2-3) : 375 - 400

← 1 2 3 4 5 →