A faster FPT algorithm for bipartite contraction
From MaRDI portal
Publication:2445333
DOI10.1016/j.ipl.2013.09.004zbMath1284.68648arXiv1305.2743OpenAlexW1832264756MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (17)
Paths to Trees and Cacti ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ The complexity of degree anonymization by graph contractions ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ An improved linear kernel for the cycle contraction problem ⋮ Reducing graph transversals via edge contractions ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
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
This page was built for publication: A faster FPT algorithm for bipartite contraction
