Efficient implementation of a minimal triangulation algorithm

DOI10.1007/3-540-45749-6_49MaRDI QIDQ4411390zbMATH OpenFDO

Authors Pinar Heggernes, Yngve Villanger

Publication date 8 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2461/24610550.htm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• Efficiently enumerating minimal triangulations
• Fast minimal triangulation algorithm using minimum degree criterion

Cited in

(11)

• Efficiently enumerating minimal triangulations
• Implementation of linear minimum area enclosing triangle algorithm. Application note
• Tree decomposition and discrete optimization problems: a survey
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• scientific article; zbMATH DE number 1305489 (Why is no real title available?)
• An algorithm for constructing locally optimal min-max triangulation
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Minimal triangulations of graphs: a survey
• A vertex incremental approach for maintaining chordality
• Lex M versus MCS-M
• Treewidth computations. I: Upper bounds

This page was built for publication: Efficient implementation of a minimal triangulation algorithm

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