Kernelization of graph Hamiltonicity: proper H-graphs
From MaRDI portal
Kernelization of graph Hamiltonicity: proper \(H\)-graphs (scientific article; zbMATH DE number 7340687)
Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- Algorithmic graph theory and perfect graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc 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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- 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
(8)- Graph Hamiltonicity parameterized by proper interval deletion set
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Intersection graphs of non-crossing paths
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Treewidth versus clique number. II: Tree-independence number
- Computing tree decompositions with small independence number
- Approximate Turing kernelization for problems parameterized by treewidth
- Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
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)
