A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph

DOI10.1137/0205012MaRDI QIDQ4124208zbMATH OpenOpenAlexFDO

Authors Tatsuo Ohtsuki

Publication date 1976

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0205012

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)

Cited in

(12)

• Lex M versus MCS-M
• On minimal augmentation of a graph to obtain an interval graph
• Minimal fill in O(\(n^{2.69}\)) time
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
• Approximating the bandwidth for asteroidal triple-free graphs
• Minimal triangulations of graphs: a survey
• On the minimum chordal completion polytope
• Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
• Optimal decomposition by clique separators
• A note on minimal d-separation trees for structural learning
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem

This page was built for publication: A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph

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