Tight double exponential lower bounds

DOI10.1007/978-981-97-2340-9_11MaRDI QIDQ6636075zbMATH OpenFDO

Authors I. A. Bliznets, Markus Hecher

Publication date 12 November 2024

Full work available at URL https://doi.org/10.1007/978-981-97-2340-9_11

zbMATH Keywords

choosabilitydouble exponentiallower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bounded-width QBF is PSPACE-complete
• Complexity of clique coloring and related problems
• Contribution to nonserial dynamic programming
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Fundamentals of parameterized complexity
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• Improved Steiner tree algorithms for bounded treewidth
• Lower Bounds for QBFs of Bounded Treewidth
• Parameterized algorithms
• Parametrized complexity theory.
• Planar Formulae and Their Uses
• Some results on (a:b)-choosability
• Treewidth with a quantifier alternation revisited
• Which problems have strongly exponential complexity?

Cited in

(5)

• Core stability in additively separable hedonic games of low treewidth
• Exact and parameterized algorithms for choosability
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Core stability in additively separable hedonic games of low treewidth
• Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

This page was built for publication: Tight double exponential lower bounds

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