Computing roots of graphs is hard
From MaRDI portal
Publication:1336641
DOI10.1016/0166-218X(94)00023-9zbMath0812.68103MaRDI QIDQ1336641
Publication date: 3 November 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
The complexity of Boolean matrix root computation ⋮ A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ A unified approach to recognize squares of split graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Local-Global Phenomena in Graphs ⋮ Strictly chordal graphs are leaf powers ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Clique complexes and graph powers ⋮ Computing square roots of graphs with low maximum degree ⋮ Biclique graphs of interval bigraphs ⋮ A characterization of line graphs that are squares of graphs ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ Complexity of finding graph roots with girth conditions ⋮ A good characterization of squares of strongly chordal split graphs ⋮ Extremal graphs for the identifying code problem ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Strongly simplicial vertices of powers of trees ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ Squares of low clique number ⋮ The square of a block graph ⋮ Exact leaf powers ⋮ 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 ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Linear-time algorithms for tree root problems ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs ⋮ Parameterized algorithms for finding square roots
Cites Work
- Unnamed Item
- Unnamed Item
- Finding EPS-graphs
- The square of every two-connected graph is Hamiltonian
- Characterization of n-path graphs and of graphs having \(n\)-th root
- Locality in Distributed Graph Algorithms
- Algorithms for Square Roots of Graphs
- A criterion for planarity of the square of a graph
- The square root of a graph
- The square root of a digraph
