Computing roots of graphs is hard

DOI10.1016/0166-218X(94)00023-9zbMATH Open0812.68103MaRDI QIDQ1336641FDOQ1336641

Authors: Rajeev Motwani, Madhu Sudan 

Publication date: 3 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• Computing square roots of graphs with low maximum degree
• scientific article; zbMATH DE number 6027233
• Algorithms for Square Roots of Graphs
• Bipartite roots of graphs
• Complexity of finding graph roots with girth conditions

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Algorithms for Square Roots of Graphs
• The square root of a graph
• Characterization of n-path graphs and of graphs having \(n\)-th root
• Locality in Distributed Graph Algorithms
• Finding EPS-graphs
• The square of every two-connected graph is Hamiltonian
• Title not available (Why is that?)
• A criterion for planarity of the square of a graph
• The square root of a digraph

Cited In (37)

• The complexity of Boolean matrix root computation
• A characterization of line graphs that are squares of graphs
• Title not available (Why is that?)
• Parameterized algorithms for finding square roots
• Hardness and structural results for half-squares of restricted tree convex bipartite graphs
• Linear-time algorithms for tree root problems
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• The square of a block graph
• Exact leaf powers
• Finding cactus roots in polynomial time
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• A good characterization of squares of strongly chordal split graphs
• A unified approach to recognize squares of split graphs
• Local-Global Phenomena in Graphs
• Clique complexes and graph powers
• Closest 4-leaf power is fixed-parameter tractable
• Complexity of finding graph roots with girth conditions
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Computing square roots of trivially perfect and threshold graphs
• Structure of squares and efficient domination in graph classes
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Strongly simplicial vertices of powers of trees
• Graph square roots of small distance from degree one graphs
• The complexity of Boolean matrix root computation
• Model checking on interpretations of classes of bounded local cliquewidth
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Finding cut-vertices in the square roots of a graph
• Finding Cactus Roots in Polynomial Time
• Extremal graphs for the identifying code problem
• Partial Characterizations of 1‐Perfectly Orientable Graphs
• Squares of low clique number
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• Strictly chordal graphs are leaf powers
• Title not available (Why is that?)
• Biclique graphs of interval bigraphs

This page was built for publication: Computing roots of graphs is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336641)