A faster FPT algorithm for bipartite contraction
From MaRDI portal
Publication:2445333
DOI10.1016/j.ipl.2013.09.004zbMath1284.68648arXiv1305.2743MaRDI QIDQ2445333
Dániel Marx, Sylvain Guillemot
Publication date: 14 April 2014
Published in: Information Processing Letters, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.2743
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
Related Items
On the Parameterized Complexity of Contraction to Generalization of Trees., Paths to Trees and Cacti, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, Reducing the vertex cover number via edge contractions, A survey of parameterized algorithms and the complexity of edge modification, Contracting to a longest path in H-free graphs, On the Parameterized Complexity of Maximum Degree Contraction Problem., Parameterized complexity of three edge contraction problems with degree constraints, On the parameterized complexity of maximum degree contraction problem, Obtaining split graphs by edge contraction, Paths to trees and cacti, On the parameterized complexity of contraction to generalization of trees, Reducing graph transversals via edge contractions, An improved linear kernel for the cycle contraction problem, The complexity of degree anonymization by graph contractions, On the parameterized complexity of grid contraction, A single exponential-time FPT algorithm for cactus contraction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On group feedback vertex set parameterized by the size of the cutset
- FPT algorithms for path-transversal and cycle-transversal problems
- Finding odd cycle transversals.
- Parameterized graph separation problems
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Chordal deletion is fixed-parameter tractable
- Proper interval vertex deletion
- An improved parameterized algorithm for the minimum node multiway cut problem
- Obtaining a planar graph by vertex deletion
- Contracting graphs to paths and trees
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- Obtaining Planarity by Contracting Few Edges
- Measuring Indifference: Unit Interval Vertex Deletion
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Interval Completion Is Fixed Parameter Tractable
- Simpler Parameterized Algorithm for OCT
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Color-coding
- Faster Parameterized Algorithms Using Linear Programming
- Planarity Allowing Few Error Vertices in Linear Time
- Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
