Polynomial-Time Algorithm for the Leafage of Chordal Graphs

DOI10.1007/978-3-642-04128-0_27zbMath1256.05233OpenAlexW2127689597MaRDI QIDQ3639254

Juraj Stacho, Michel A. Habib

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04128-0_27

zbMATH Keywords

intersection graphpolynomial time algorithmchordal graphleafagetree modelhost treecollection of subtrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (18)

The neighborhood polynomial of chordal graphs ⋮ Strictly interval graphs: characterization and linear time recognition ⋮ Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ An efficient algorithm for counting Markov equivalent DAGs ⋮ Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ The Neighborhood Polynomial of Chordal Graphs ⋮ The firebreak problem ⋮ Reduced clique graphs of chordal graphs ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ The vertex leafage of chordal graphs ⋮ On asteroidal sets in chordal graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Domination and Cut Problems on Chordal Graphs with Bounded Leafage ⋮ A Decomposition Theorem for Chordal Graphs and its Applications ⋮ k-separator chordal graphs: leafage and subfamilies

This page was built for publication: Polynomial-Time Algorithm for the Leafage of Chordal Graphs