Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2
| Autor: | Daniël Paulusma, Pinar Heggernes, Paloma T. Lima, Dieter Kratsch, Petr A. Golovach |
|---|---|
| Přispěvatelé: | Laboratoire de Génie Informatique, de Production et de Maintenance (LGIPM), Université de Lorraine (UL) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Class (set theory)
General Computer Science Applied Mathematics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Computer Science Applications [SPI.AUTO]Engineering Sciences [physics]/Automatic Perspective (geometry) Pathwidth Square root 010201 computation theory & mathematics Outerplanar graph Theory of computation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm ComputingMilieux_MISCELLANEOUS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Algorithmica Algorithmica, Springer Verlag, 2019, 81 (7), pp.2795-2828. ⟨10.1007/s00453-019-00555-y⟩ Algorithmica, 2019, Vol.81(7), pp.2795-2828 [Peer Reviewed Journal] |
| ISSN: | 0178-4617 1432-0541 |
| DOI: | 10.1007/s00453-019-00555-y⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink