On the Equivalence among Problems of Bounded Width

DOI10.1007/978-3-662-48350-3_63zbMath1466.68043arXiv1509.01014OpenAlexW2964333832MaRDI QIDQ3452838

Yuichi Yoshida, Yoichi Iwata

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.01014

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on exact algorithms for vertex ordering problems on graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Which problems have strongly exponential complexity?
• Describing parameterized complexity classes
• Linear time solvable optimization problems on graphs of bounded clique-width
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Exact Algorithms for Maximum Independent Set
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• On Problems as Hard as CNF-SAT
• Computational Complexity
• Determinant Sums for Undirected Hamiltonicity
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• On the complexity of \(k\)-SAT

This page was built for publication: On the Equivalence among Problems of Bounded Width