Name
Title | ||
|---|---|---|
Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs. |
Abstract | ||
|---|---|---|
The square of a graph G, denoted G 2 , is obtained from G by putting an edge between two distinct vertices whenever their distance is two. Then G is called a square root of G 2 . Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph.We present a polynomial time algorithm that decides whether a given graph has a Ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges.In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2015.07.060 | Theoretical Computer Science |
Keywords | DocType | Volume |
Square of graph,Square of Ptolemaic graph,Square of split graph,Recognition algorithm | Journal | 602 |
Issue | ISSN | Citations |
C | 0304-3975 | 4 |
PageRank | References | Authors |
0.42 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Van Bang Le | 1 | 481 | 66.67 |
| Andrea Oversberg | 2 | 9 | 1.53 |
| Oliver Schaudt | 3 | 95 | 21.74 |