Maximum cardinality search for computing minimal triangulations of graphs

DOI10.1007/s00453-004-1084-3zbMath1090.68080OpenAlexW2067692416MaRDI QIDQ1882406

Anne Berry, Pinar Heggernes, Jean R. S. Blair, Barry W. Peyton

Publication date: 1 October 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1084-3

zbMATH Keywords

chordal graphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Lex M versus MCS-M, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Unnamed Item, Graph extremities defined by search algorithms, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, Objective Bayesian Nets for Integrating Consistent Datasets, Linearizing partial search orders, 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, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms, Tractability of most probable explanations in multidimensional Bayesian network classifiers, Solving Graph Problems via Potential Maximal Cliques, A decomposition-based algorithm for learning the structure of multivariate regression chain graphs, Tree decomposition and discrete optimization problems: a survey, A new algorithm for decomposition of graphical models, An improved Hara-Takamura procedure by sharing computations on junction tree in Gaussian graphical models, Treewidth computations. I: Upper bounds, A note on minimal d-separation trees for structural learning, Fast minimal triangulation algorithm using minimum degree criterion, Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network, Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition, Avoidable vertices and edges in graphs: existence, characterization, and applications, Learning tractable Bayesian networks in the space of elimination orders, Attachment centrality: measure for connectivity in networks, Bayesian networks: the minimal triangulations of a graph, Tree decompositions and social graphs, Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure, Extremities and orderings defined by generalized graph search algorithms, Analyses and implementations of chordality-preserving top-down algorithms for triangular decomposition