Separator orders in interval, cocomparability, and AT-free graphs

DOI10.1016/J.DAM.2011.01.014MaRDI QIDQ534331zbMATH OpenOpenAlexFDO

Authors Jonathan Backer

Publication date 17 May 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.01.014

zbMATH Keywords

graphpartial orderminimal separator

Mathematics Subject Classification ID

Connectivity (05C40)

Cites work

• scientific article; zbMATH DE number 3458685 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1522927 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Asteroidal Triple-Free Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Counting clique trees and computing perfect elimination schemes in parallel
• How to use the minimal separators of a graph for its chordal triangulation
• Incidence matrices and interval graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Listing all Minimal Separators of a Graph
• Representation of a finite graph by a set of intervals on the real line
• Representations of chordal graphs as subtrees of a tree
• Separability generalizes Dirac's theorem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory
• Transitiv orientierbare Graphen
• Treewidth. Computations and approximations
• Triangulating graphs without asteroidal triples

Cited in

(3)

• Bisimplicial separators
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs

This page was built for publication: Separator orders in interval, cocomparability, and AT-free graphs

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