Bipartite roots of graphs

DOI10.1145/1150334.1150337MaRDI QIDQ2944512zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cited in

(24)

• scientific article; zbMATH DE number 7324127 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 6469239 (Why is no real title available?)
• Computing roots of graphs is hard
• Finding cactus roots in polynomial time
• Finding cactus roots in polynomial time
• A unified approach to recognize squares of split graphs
• Characterizing and recognizing exact-distance squares of 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
• Parameterized leaf power recognition via embedding into graph products
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Finding cut-vertices in the square roots of a graph
• On the square coloring of comparability graphs

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)