Subexponential time algorithms for finding small tree and path decompositions

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)

Samenvatting

The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k¿=¿4. In this paper we present algorithms that solve both problems for fixed k in 2^O(n/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.
Originele taal-2Engels
TitelAlgorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)
RedacteurenN. Bansal, I. Finocchi
Plaats van productieBerlin
UitgeverijSpringer
Pagina's179-190
ISBN van geprinte versie978-3-662-48349-7
DOI's
StatusGepubliceerd - 2015

Publicatie series

NaamLecture Notes in Computer Science
Volume9294
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Subexponential time algorithms for finding small tree and path decompositions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit