Separability generalizes Dirac's theorem

DOI10.1016/S0166-218X(98)00005-5zbMath0901.05079OpenAlexW1986225245MaRDI QIDQ1392561

Jean-Paul Bordat, Anne Berry

Publication date: 17 November 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

moplexmoduletriangulated graphlexicographic breadth-first-search

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (27)

Minimal triangulations of graphs: a survey ⋮ Representing a concept lattice by a graph ⋮ Graph searches and their end vertices ⋮ Graph extremities defined by search algorithms ⋮ Computing a clique tree with the algorithm maximal label search ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Robinsonian matrices: recognition challenges ⋮ Shifting paths to avoidable ones ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Computing and listing avoidable vertices and paths ⋮ Computing and listing avoidable vertices and paths ⋮ Finding biclique partitions of co-chordal graphs ⋮ A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph ⋮ Avoidable paths in graphs ⋮ Moplex orderings generated by the LexDFs algorithm ⋮ Minimal proper interval completions ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Asteroidal triples of moplexes ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Minimal interval completion through graph exploration ⋮ Junction trees of general graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Extremities and orderings defined by generalized graph search algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Some aspects of perfect elimination orderings in chordal graphs
• Decomposition by clique separators
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Meyniel weakly triangulated graphs. II: A theorem of Dirac
• On the semi-perfect elimination
• Incidence matrices and interval graphs
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect Elimination and Chordal Bipartite Graphs

This page was built for publication: Separability generalizes Dirac's theorem