A unified approach to recognize squares of split graphs

DOI10.1016/j.tcs.2016.07.037zbMath1349.05328OpenAlexW2181963588MaRDI QIDQ313959

Oliver Schaudt, Van Bang Le, Andrea Oversberg

Publication date: 12 September 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.07.037

zbMATH Keywords

square of graphssquare of split graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (6)

A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Graph square roots of small distance from degree one graphs

Cites Work

• Arboricity, \(h\)-index, and dynamic algorithms
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Probe threshold and probe trivially perfect graphs
• Computing roots of graphs is hard
• Efficient graph representations
• Decomposition of balanced matrices
• A good characterization of squares of strongly chordal split graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• Computing square roots of trivially perfect and threshold graphs
• On balanced graphs
• Split Graphs Having Dilworth Number Two
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Hardness Results and Efficient Algorithms for Graph Powers
• Unnamed Item
• Unnamed Item

This page was built for publication: A unified approach to recognize squares of split graphs