Computing the treewidth and the minimum fill-in with the modular decomposition

DOI10.1007/s00453-003-1026-5zbMath1045.68151OpenAlexW2055691408WikidataQ59567877 ScholiaQ59567877MaRDI QIDQ1402225

Udi Rotics, Hans L. Bodlaender

Publication date: 19 August 2003

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dspace.library.uu.nl/handle/1874/23972

zbMATH Keywords

Polynomial algorithmsGraph algorithmsModular decompositionTreewidthMinimal separatorsMinimum fill-in

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Counting spanning trees using modular decomposition ⋮ Acyclic and star colorings of cographs ⋮ Solving some NP-complete problems using split decomposition ⋮ Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Minimal separators in extended \(P_4\)-laden graphs ⋮ Counting Spanning Trees in Graphs Using Modular Decomposition ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: Computing the treewidth and the minimum fill-in with the modular decomposition