Moplex orderings generated by the LexDFs algorithm

DOI10.1016/J.DAM.2013.02.028MaRDI QIDQ2446863zbMATH OpenOpenAlexFDO

Authors S. J. Xu, Xianyue Li, Ronghua Liang

Publication date 22 April 2014

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

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

zbMATH Keywords

chordal graphDFSLexBFsLexDFsmoplex

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Moplex elimination orderings
• Separability generalizes Dirac's theorem
• LexBFS-orderings and powers of chordal graphs
• Graph-Theoretic Concepts in Computer Science
• Computing a clique tree with the algorithm maximal label search

Cites work

• A characterisation of rigid circuit graphs
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph extremities defined by search algorithms
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 751126 (Why is no real title available?)
• Incidence matrices and interval graphs
• Minimum average distance clique trees
• On rigid circuit graphs
• Separability generalizes Dirac's theorem
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Cited in

(9)

• Separability generalizes Dirac's theorem
• Computing a clique tree with the algorithm maximal label search
• Robinsonian matrices: recognition challenges
• Moplex elimination orderings
• Organizing the atoms of the clique separator decomposition into an atom tree
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Finding biclique partitions of co-chordal graphs
• Graphs with at most two moplexes
• Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

This page was built for publication: Moplex orderings generated by the LexDFs algorithm

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