Recognizing Proper Tree-Graphs

DOI10.4230/lipics.ipec.2020.8arXiv2011.11670OpenAlexW3115462601MaRDI QIDQ6089652

Dušan Knop, Petr A. Golovach, Steven Chaplick, Tim A. Hartmann

Publication date: 13 November 2023

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

zbMATH Keywords

recognitionintersection graphsfixed-parameter tractability\(H\)-graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Precoloring extension. I: Interval graphs
• Combinatorial problems on \(H\)-graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• On the tractability of optimization problems on \(H\)-graphs
• Mim-width. II. The feedback vertex set problem
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• Extending partial representations of subclasses of chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• The leafage of a chordal graph
• Graph Classes: A Survey
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Topology of Thin Film RC Circuits
• On \(H\)-topological intersection graphs
• Chordal graphs and their clique graphs

This page was built for publication: Recognizing Proper Tree-Graphs