Algorithms for Square Roots of Graphs
From MaRDI portal
Publication:4764347
DOI10.1137/S089548019120016XzbMath0821.05052MaRDI QIDQ4764347
Yaw-Ling Lin, Steven S. Skiena
Publication date: 4 May 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (32)
OPTIMAL RADIOCOLORING OF TREES ⋮ Computing roots of graphs is hard ⋮ A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ Complexity of the Packing Coloring Problem for Trees ⋮ On powers of \(m\)-trapezoid graphs ⋮ Strictly chordal graphs are leaf powers ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ Biclique graphs of interval bigraphs ⋮ A characterization of line graphs that are squares of graphs ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Distance three labelings of trees ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ Complexity of finding graph roots with girth conditions ⋮ Square roots of minor closed graph classes ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Squares of low clique number ⋮ The square of a block graph ⋮ Exact leaf powers ⋮ Fixed-parameter complexity of \(\lambda\)-labelings ⋮ Finding cut-vertices in the square roots of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Graph square roots of small distance from degree one graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Radiocoloring in planar graphs: Complexity and approximations ⋮ Linear-time algorithms for tree root problems ⋮ Parameterized algorithms for finding square roots
This page was built for publication: Algorithms for Square Roots of Graphs
