Bipartite roots of graphs
From MaRDI portal
Publication:2944512
DOI10.1145/1150334.1150337zbMath1321.05209OpenAlexW2058105885MaRDI QIDQ2944512
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1150334.1150337
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
A linear kernel for finding square roots of almost planar graphs ⋮ On the square coloring of comparability graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ A characterization of line graphs that are squares of graphs ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Complexity of finding graph roots with girth conditions ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ The square of a block graph ⋮ 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 ⋮ 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 ⋮ Unnamed Item ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Linear-time algorithms for tree root problems ⋮ Parameterized algorithms for finding square roots
This page was built for publication: Bipartite roots of graphs
