On the parameterized complexity of finding separators with non-hereditary properties
From MaRDI portal
Publication:494799
DOI10.1007/s00453-014-9868-6zbMath1328.68094OpenAlexW2096291975MaRDI QIDQ494799
Pim van 't Hof, Neeldhara Misra, Yngve Villanger, Pinar Heggernes, Dániel Marx
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9868-6
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- FPT algorithms for path-transversal and cycle-transversal problems
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Parameterized graph separation problems
- Constant ratio fixed-parameter approximation of the edge multicut problem
- On the parameterized complexity of multiple-interval graph problems
- On problems without polynomial kernels
- Decomposition by clique separators
- A logical approach to multicut problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Finding small balanced separators
- Finding small separators in linear time via treewidth reduction
- Treewidth reduction for constrained separation and bipartization problems
- Minimizing Movement: Fixed-Parameter Tractability
- Color-coding
- Reducibility among Combinatorial Problems
- (Meta) Kernelization
- On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
- Bidimensionality and Geometric Graphs
- Multicut is FPT
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- The steiner problem in graphs
- Steiner tree problems
This page was built for publication: On the parameterized complexity of finding separators with non-hereditary properties
