Parameterized Complexity of Eulerian Deletion Problems
From MaRDI portal
Publication:3104771
DOI10.1007/978-3-642-25870-1_13zbMath1341.05141OpenAlexW55260560MaRDI QIDQ3104771
Ildikó Schlotter, Marek Cygan, Marcin Pilipczuk, Dániel Marx, Michał Pilipczuk
Publication date: 16 December 2011
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: http://europepmc.org/articles/pmc3883159
Extremal problems in graph theory (05C35) Randomized algorithms (68W20) Eulerian and Hamiltonian graphs (05C45)
Related Items (6)
What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ Parameterized Eulerian strong component arc deletion problem on tournaments ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Editing to a graph of given degrees
Cites Work
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- Parameterized algorithms for feedback set problems and their duals in tournaments
- On the complexity of paths avoiding forbidden pairs
- Chordal deletion is fixed-parameter tractable
- Parameterized complexity of finding regular induced subgraphs
- The node-deletion problem for hereditary properties is NP-complete
- Finding minimum-cost flows by double scaling
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Competing provers yield improved Karp-Lipton collapse results
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized complexity of the induced subgraph problem in directed graphs
- Additive approximation for edge-deletion problems
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- NP-completeness results for edge modification problems
- Efficient Algorithms for Eulerian Extension
- A Quartic Kernel for Pathwidth-One Vertex Deletion
- Computing the Deficiency of Housing Markets with Duplicate Houses
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Wheel-Free Deletion Is W[2-Hard]
- Parameterized Complexity of Even/Odd Subgraph Problems
- Two Edge Modification Problems without Polynomial Kernels
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Color-coding
- Matching, Euler tours and the Chinese postman
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Fast FPT-Algorithms for Cleaning Grids
- Complexity classification of some edge modification problems
This page was built for publication: Parameterized Complexity of Eulerian Deletion Problems
