Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs

DOI10.1016/j.tcs.2015.07.060zbMath1330.05148arXiv1402.0024OpenAlexW1553451955MaRDI QIDQ497674

Van Bang Le, Oliver Schaudt, Andrea Oversberg

Publication date: 25 September 2015

Published in: Theoretical Computer Science, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0024

zbMATH Keywords

recognition algorithmsquare of graphsquare of a graphsquare of a Ptolemaic graphsquare of a split graphsquare of Ptolemaic graphsquare of split graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

A unified approach to recognize squares of split 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 ⋮ 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 ⋮ Finding Cactus Roots in Polynomial Time ⋮ Unnamed Item ⋮ Parameterized algorithms for finding square roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Uniqueness of graph square roots of girth six
• Completely separable graphs
• The square of a block graph
• Distance-hereditary graphs
• Computing roots of graphs is hard
• Algorithmic graph theory and perfect graphs
• Powers of distance-hereditary graphs
• A good characterization of squares of strongly chordal split graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• Complexity of finding graph roots with girth conditions
• Computing square roots of trivially perfect and threshold graphs
• Sparse Square Roots
• Bipartite roots of graphs
• Large-Girth Roots of Graphs
• Doubly Lexical Orderings of Matrices
• A characterization of ptolemaic graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Linear-Time Algorithms for Tree Root Problems
• Hardness Results and Efficient Algorithms for Graph Powers

This page was built for publication: Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs