Kernelization of graph Hamiltonicity: proper H-graphs

DOI10.1137/19M1299001MaRDI QIDQ4986812zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, Peter Zeman

Publication date 28 April 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/19m1299001

zbMATH Keywords

path coverkernelizationcycle coverproper \(H\)-graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Kernel bounds for path and cycle problems
• Kernel bounds for path and cycle problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Algorithmic graph theory and perfect graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An application of simultaneous diophantine approximation in combinatorial optimization
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Color-coding
• Combinatorial problems on \(H\)-graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Fundamentals of parameterized complexity
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• Kernel bounds for path and cycle problems
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Kernelization. Theory of parameterized preprocessing
• Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Narrow sieves for parameterized paths and packings
• On \(H\)-topological intersection graphs
• On problems without polynomial kernels
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Paths in interval graphs and circular arc graphs
• Precoloring extension. I: Interval graphs
• Proper interval graphs and the guard problem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The complexity ecology of parameters: An illustration using bounded max leaf number

Cited in

(5)

• Treewidth versus clique number. II: Tree-independence number
• Intersection graphs of non-crossing paths
• Graph Hamiltonicity parameterized by proper interval deletion set
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Kernelization of graph Hamiltonicity: proper \(H\)-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986812)