Exact Algorithms for Treewidth and Minimum Fill-In

DOI10.1137/050643350zbMath1163.05320WikidataQ60488730 ScholiaQ60488730MaRDI QIDQ3631902

Dieter Kratsch, Fedor V. Fomin, Yngve Villanger, Ioan Todinca

Publication date: 22 June 2009

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

Full work available at URL: http://hdl.handle.net/1956/1151

zbMATH Keywords

treewidth; minimal triangulation; fill-in; exact exponential algorithm; minimal separators; potential maximal clique

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)