On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT

DOI10.1007/978-3-662-53174-7_33zbMath1417.05213OpenAlexW948964816MaRDI QIDQ5890956

Bart M. P. Jansen

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_33

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Parameterized complexity of path set packing ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Two-layer planarization parameterized by feedback edge set
• Exact algorithms and applications for tree-like Weighted Set Cover
• A kernelization algorithm for \(d\)-hitting set
• Solving NP-hard problems in 'almost trees': vertex cover
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Which problems have strongly exponential complexity?
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Incompressibility through Colors and IDs
• Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT