Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs

1989/01/01 by Marek Chrobák, Marek Chrobak, Joseph Naor +1 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Binary tree #Block graph #Chordal graph #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Indifference graph #Interconnection Networks and Systems #Line graph #Mathematics #Pathwidth #Spanning tree #Split graph #Treewidth #Trémaux tree

paper · doi:10.1007/3-540-51542-9_13

crossref issued 1989/01/01 · crossref published 1989/01/01 · crossref published-print 1989/01/01 · openalex publication_date 1989/01/01 · crossref published-online 2005/05/26 · crossref created 2012/02/25 · crossref deposited 2021/04/27 · crossref indexed 2024/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• On maximal independent sets of vertices in claw-free graphs
• Matching is as easy as matrix inversion
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
• A max m,n algorithm for determining the graph H from its line graph G
• The matching problem for bipartite graphs with polynomially bounded permanents is in NC
• Congruent Graphs and the Connectivity of Graphs
• Paths, Trees, and Flowers

Cited by

• Claw-free graph [wikipedia]