Name
Abstract | ||
|---|---|---|
Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class \({{\mathcal {H}}}\). There are both polynomial-time solvable and NP-complete results in this direction, depending on \({{\mathcal {H}}}\). We present a general framework for the problem if \(\mathcal{H}\) is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where \({{\mathcal {H}}}\) is the class of outerplanar graphs and \({{\mathcal {H}}}\) is the class of graphs of pathwidth at most 2. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-68705-6_21 | WG |
Keywords | DocType | Volume |
Graph square root, Outerplanar graphs, Graphs of pathwidth 2 | Conference | abs/1703.05102 |
Issue | ISSN | Citations |
7 | 1432-0541 | 2 |
PageRank | References | Authors |
0.37 | 19 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Dieter Kratsch | 3 | 1957 | 146.89 |
| Paloma T. Lima | 4 | 6 | 3.53 |
| Daniel Paulusma | 5 | 102 | 14.89 |