Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

DOI10.1016/0022-247X(76)90182-7zbMATH Open0371.65006MaRDI QIDQ1243572FDOQ1243572

Authors Tatsuo Ohtsuki, Lap Kit Cheung, Toshio Fujisawa 

Publication date 1976

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cites work

• scientific article; zbMATH DE number 3322854 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• On rigid circuit graphs
• Representation of a finite graph by a set of intervals on the real line
• The Use of Linear Graphs in Gauss Elimination
• The inverse M-matrix problem
• Triangulated graphs and the elimination process

Cited in

(29)

• On the minimum chordal completion polytope
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• Minimal triangulations of graphs: a survey
• All roads lead to Rome -- new search methods for the optimal triangulation problem
• Standard imsets for undirected and chain graphical models
• Extremities and orderings defined by generalized graph search algorithms
• Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
• Decomposition by clique separators
• Graph extremities defined by search algorithms
• On minimal augmentation of a graph to obtain an interval graph
• Computing and listing avoidable vertices and paths
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• Bounds for cell entries in contingency tables given marginal totals and decomposable graphs
• Graphs with at most two moplexes
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• Algorithms for convex hull finding in undirected graphical models
• A note on minimal d-separation trees for structural learning
• An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
• Searching for better fill-in
• Efficiently enumerating minimal triangulations
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Shifting paths to avoidable ones
• Minimum fill-in of sparse graphs: kernelization and approximation
• Marginal Markov subgraph of Bayesian network and its applications
• A practical algorithm for making filled graphs minimal
• Optimal decomposition by clique separators
• Separability generalizes Dirac's theorem
• Computing and listing avoidable vertices and paths

This page was built for publication: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

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