Polynomial-Time Algorithm for the Leafage of Chordal Graphs

DOI10.1007/978-3-642-04128-0_27MaRDI QIDQ3639254zbMATH OpenOpenAlexFDO

Authors Juraj Stacho, M. 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

chordal graphcollection of subtreeshost treeintersection graphleafagepolynomial time algorithmtree model

Mathematics Subject Classification ID

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

Recommendations

• The leafage of a chordal graph
• Determining possible sets of leaves for spanning trees of dually chordal graphs.
• The vertex leafage of chordal graphs
• k-separator chordal graphs: leafage and subfamilies
• Linear algorithms for chordal graphs of bounded directed vertex leafage

Cited in

(25)

• 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
• Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs
• On the tractability of optimization problems on \(H\)-graphs
• The vertex leafage of chordal graphs
• On asteroidal sets in chordal graphs
• An efficient algorithm for counting Markov equivalent DAGs
• Linear algorithms for chordal graphs of bounded directed vertex leafage
• A decomposition theorem for chordal graphs and its applications
• k-separator chordal graphs: leafage and subfamilies
• Strictly interval graphs: characterization and linear time recognition
• Reduced clique graphs of chordal graphs
• The leafage of a chordal graph
• On the tractability of optimization problems on \(H\)-graphs
• On k-trees with given leafages
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
• The Neighborhood Polynomial of Chordal Graphs
• The firebreak problem
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Domination and cut problems on chordal graphs with bounded leafage
• The neighborhood polynomial of chordal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639254)