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

DOI10.1016/0022-247X(76)90182-7zbMath0371.65006MaRDI QIDQ1243572

Toshio Fujisawa, Lap Kit Cheung, Tatsuo Ohtsuki

Publication date: 1976

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

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• The inverse M-matrix problem
• Triangulated graphs and the elimination process
• The Use of Linear Graphs in Gauss Elimination
• Representation of a finite graph by a set of intervals on the real line
• A Characterization of Comparability Graphs and of Interval Graphs