Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2

被引：2

作者：

Golovach, Petr A. ^{[1
]}

Heggernes, Pinar ^{[1
]}

Kratsch, Dieter ^{[2
]}

Lima, Paloma T. ^{[1
]}

Paulusma, Daniel ^{[3
]}

机构：

[1] Univ Bergen, Dept Informat, PB 7803, N-5020 Bergen, Norway

[2] Univ Lorraine, Lab Informat Theor & Appl, F-57045 Metz 01, France

[3] Univ Durham, Sch Engn & Comp Sci, Durham DH1 3LE, England

来源：

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017) | 2017年 / 10520卷

关键词：

SQUARE ROOTS; POLYNOMIAL-TIME; SPLIT GRAPHS; TREEWIDTH; TREE;

D O I：

10.1007/978-3-319-68705-6_21

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding whether a given graph has a square root that belongs to a particular graph class. There are both polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.

引用

页码：275 / 288

页数：14

共 46 条

[31] Fly-automata for checking MSO2 graph properties
Courcelle, Bruno
DISCRETE APPLIED MATHEMATICS, 2018, 245 : 236 - 252
[32] THE SQUARE MAPPING GRAPH OF 2 x 2 MATRIX RINGS OVER PRIME FIELDS
Tang, Gaohua
Zhang, Hengbin
Wei, Yangjiang
ARS COMBINATORIA, 2019, 143 : 59 - 75
[33] Star Coloring and Tree-width of the Kneser Graph KG(n, 2)
Omoomi, Behnaz
Roshanbin, Elham
UTILITAS MATHEMATICA, 2017, 102 : 149 - 160
[34] A 3/2-approximation algorithm for some minimum-cost graph problems
Couetoux, Basile
Davis, James M.
Williamson, David P.
MATHEMATICAL PROGRAMMING, 2015, 150 (01) : 19 - 34
[35] Major contribution of grass roots to soil carbon pools and CO2 fluxes in a mesic savanna
February, Edmund
Pausch, Johanna
Higgins, Steven I.
PLANT AND SOIL, 2020, 454 (1-2) : 207 - 215
[36] Excluding any graph as a minor allows a low tree-width 2-coloring
DeVos, M
Ding, GL
Oporowski, B
Sanders, DP
Reed, B
Seymour, P
Vertigan, D
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 91 (01) : 25 - 41
[37] The 1/3-2/3 Conjecture for Ordered Sets whose Cover Graph is a Forest
Imed Zaguia
Order, 2019, 36 : 335 - 347
[38] Optimal Representation of Large-Scale Graph Data Based on K2-Tree
Liang Chang
Xiangxuan Zeng
Zhoubo Xu
Junyan Qian
Tianlong Gu
Houbing Song
Wireless Personal Communications, 2017, 95 : 2271 - 2284
[39] The 1/3-2/3 Conjecture for Ordered Sets whose Cover Graph is a Forest
Zaguia, Imed
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2019, 36 (02): : 335 - 347
[40] Generating the Triangulations of the Torus with the Vertex-Labeled Complete 4-Partite Graph K2,2,2,2
Lawrencenko, Serge
Magomedov, Abdulkarim M.
SYMMETRY-BASEL, 2021, 13 (08):

← 1 2 3 4 5 →