Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
From MaRDI portal
Publication:988694
DOI10.1016/J.JDA.2010.02.002zbMATH Open1192.90239OpenAlexW2016465035MaRDI QIDQ988694FDOQ988694
Authors: Ignasi Sau, Dimitrios M. Thilikos 
Publication date: 18 August 2010
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2010.02.002
Recommendations
- Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
- Subexponential Parameterized Algorithms
- Subexponential parameterized algorithms
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
graph minorsparameterized complexityplanar graphssubexponential algorithmbidimensionalitybranch decompositionCatalan structures
Cites Work
- Title not available (Why is that?)
- Matching theory
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Parametrized complexity theory.
- Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
- Quickly excluding a planar graph
- Supereulerian graphs: A survey
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Title not available (Why is that?)
- New upper bounds on the decomposability of planar graphs
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Title not available (Why is that?)
- Subexponential Parameterized Algorithms
- Algorithms – ESA 2005
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
Cited In (16)
- On computing the Hamiltonian index of graphs
- A subset spanner for Planar graphs, with application to subset TSP
- On Computing the Hamiltonian Index of Graphs
- Induced packing of odd cycles in planar graphs
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Confronting intractability via parameters
- Title not available (Why is that?)
- Faster parameterized algorithms for minor containment
- Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Fixed-parameter tractability of treewidth and pathwidth
- Parameterized complexity of finding small degree-constrained subgraphs
- On the approximability of some degree-constrained subgraph problems
- Dynamic programming for graphs on surfaces
This page was built for publication: Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q988694)
