Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
DOI10.1137/19M1299001zbMath1476.68198OpenAlexW3157294248MaRDI QIDQ4986812
Dušan Knop, Peter Zeman, Petr A. Golovach, Steven Chaplick, Fedor V. Fomin
Publication date: 28 April 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1299001
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Polynomial kernels for weighted problems
- Fundamentals of parameterized complexity
- Kernel bounds for path and cycle problems
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- The complexity ecology of parameters: An illustration using bounded max leaf number
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- On problems without polynomial kernels
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian circuits in interval graphs
- An application of simultaneous diophantine approximation in combinatorial optimization
- Precoloring extension. I: Interval graphs
- Paths in interval graphs and circular arc graphs
- Proper interval graphs and the guard problem
- Combinatorial problems on \(H\)-graphs
- Algorithmic graph theory and perfect graphs
- HAMILTONian circuits in chordal bipartite graphs
- On the tractability of optimization problems on \(H\)-graphs
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Narrow sieves for parameterized paths and packings
- Parameterized edge Hamiltonicity
- Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
- Faster Algebraic Algorithms for Path and Packing Problems
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Graph Classes: A Survey
- Deferred-query: An efficient approach for some problems on interval graphs
- Color-coding
- Kernelization
- Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- On \(H\)-topological intersection graphs
This page was built for publication: Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
