Parameterized complexity of Eulerian deletion problems
From MaRDI portal
Publication:2441593
DOI10.1007/s00453-012-9667-xzbMath1284.05157OpenAlexW2026720321WikidataQ37442987 ScholiaQ37442987MaRDI QIDQ2441593
Marcin Pilipczuk, Marek Cygan, Michał Pilipczuk, Ildikó Schlotter, Dániel Marx
Publication date: 25 March 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9667-x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Eulerian and Hamiltonian graphs (05C45)
Related Items (20)
Deterministic Truncation of Linear Matroids ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Editing to a Planar Graph of Given Degrees ⋮ Plane augmentation of plane graphs to meet parity constraints ⋮ Finding even subgraphs even faster ⋮ Editing to Eulerian graphs ⋮ Quantum encoding of dynamic directed graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Eulerian walks in temporal graphs ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Graph editing to a given degree sequence ⋮ Graph Editing to a Given Degree Sequence ⋮ Editing to a planar graph of given degrees ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations ⋮ Complexity of some arc-partition problems for digraphs ⋮ Two edge-disjoint paths with length constraints ⋮ Directed graph encoding in quantum computing supporting edge-failures ⋮ Königsberg sightseeing: Eulerian walks in temporal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of even/odd subgraph problems
- 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
- On the parameterized complexity of multiple-interval graph problems
- 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
- 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
- Wheel-Free Deletion Is W[2-Hard]
- Two Edge Modification Problems without Polynomial Kernels
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Color-coding
- Matching, Euler tours and the Chinese postman
- The Parameterized Complexity of the Unique Coverage Problem
- 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
