zbMATH — the first resource for mathematics

Minimal elimination ordering inside a given chordal graph. (English) Zbl 0886.05103
Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 132-143 (1997).
Let be given a graph \(G=(V,E)\) and a chordal supergraph \((V,E_2)\). In time \(O(|V||E|)\) one can compute a chordal graph \((V,E_1)\) with \(E \subseteq E_1 \subseteq E_2\) such that for all \(E'\) with \(E \subseteq E' \subset E_1\) the graph \((V,E')\) is not chordal.
For the entire collection see [Zbl 0877.00011].
Reviewer: H.Müller (Jena)

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity