Exact Algorithms for Treewidth and Minimum Fill-In | Zendy

Fedor V. Fomin | Zendy; Dieter Kratsch | Zendy; Ioan Todinca | Zendy; Yngve Villanger | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Exact Algorithms for Treewidth and Minimum Fill-In

Author(s) -

Fedor V. Fomin,

Dieter Kratsch,

Ioan Todinca,

Yngve Villanger

Publication year - 2008

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/050643350

Subject(s) - treewidth , combinatorics , mathematical proof , vertex (graph theory) , mathematics , partial k tree , graph , discrete mathematics , 1 planar graph , algorithm , pathwidth , chordal graph , line graph , geometry

We show that the treewidth and the minimum fill-in of an $n$-vertex graph can be computed in time $\mathcal{O}(1.8899^n)$. Our results are based on combinatorial proofs that an $n$-vertex graph has $\mathcal{O}(1.7087^n)$ minimal separators and $\mathcal{O}(1.8135^n)$ potential maximal cliques. We also show that for the class of asteroidal triple-free graphs the running time of our algorithms can be reduced to $\mathcal{O}(1.4142^n)$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research