Bipartite roots of graphs

DOI10.1145/1150334.1150337zbMATH Open1321.05209OpenAlexW2058105885WikidataQ130971118 ScholiaQ130971118MaRDI QIDQ2944512FDOQ2944512

Authors: Lap Chi Lau 

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

Recommendations

• scientific article; zbMATH DE number 6469239
• scientific article; zbMATH DE number 6027233
• Complexity of finding graph roots with girth conditions
• A unified approach to recognize squares of split graphs
• Algorithms for Square Roots of Graphs

zbMATH Keywords

bipartite graphsgraph powersgraph roots

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (24)

• A characterization of line graphs that are squares of graphs
• Parameterized algorithms for finding square roots
• Linear-time algorithms for tree root problems
• The square of a block graph
• Title not available (Why is that?)
• Computing roots of graphs is hard
• Finding cactus roots in polynomial time
• Finding cactus roots in polynomial time
• Characterizing and recognizing exact-distance squares of graphs
• A unified approach to recognize squares of split graphs
• Constrained representations of map graphs and half-squares
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Closest 4-leaf power is fixed-parameter tractable
• Complexity of finding graph roots with girth conditions
• Computing square roots of trivially perfect and threshold graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Finding cut-vertices in the square roots of a graph
• Parameterized leaf power recognition via embedding into graph products
• On the square coloring of comparability graphs
• Title not available (Why is that?)

This page was built for publication: Bipartite roots of graphs

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