Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

DOI10.1137/22m1518943OpenAlexW3005984602MaRDI QIDQ6170447

Céline M. F. Swennenhuis, Michał Pilipczuk, Jesper Nederlof, Karol Węgrzycki

Publication date: 10 August 2023

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

Full work available at URL: https://doi.org/10.1137/22m1518943

zbMATH Keywords

connectivityHamiltonian cyclepolynomial spacetreedepth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Matching is as easy as matrix inversion
• Clifford algebras meet tree decompositions
• Graph minors. XIII: The disjoint paths problem
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
• Branch-depth: generalizing tree-depth of graphs
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Space saving by dynamic algebraization based on tree-depth
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• Saving space by algebraization
• Planar k-Path in Subexponential Time and Polynomial Space
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
• Cut and Count and representative sets on branch decompositions
• A Faster Parameterized Algorithm for Treedepth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms

This page was built for publication: Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space