Cover Image

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Kratsch, Stefan
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient parameterized approximation
by: Kratsch, Stefan, et al.
Published: (2025)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
by: Bojikian, Narek, et al.
Published: (2023)

On polynomial kernelization for Stable Cutset
by: Kratsch, Stefan, et al.
Published: (2024)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

Counting perfect matchings and Hamiltonian cycles faster
by: Li, Baitian
Published: (2023)

Boundaried Kernelization via Representative Sets
by: Antipov, Leonid, et al.
Published: (2025)

Boundaried Kernelization
by: Antipov, Leonid, et al.
Published: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

Local search for valued constraint satisfaction parameterized by treedepth
by: Kaznatcheev, Artem
Published: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Faster parameterized algorithm for 3-Hitting Set
by: Tsur, Dekel
Published: (2025)

Minimum sum vertex cover: kernelization and parameterized algorithms
by: Cao, Yixin, et al.
Published: (2024)

Approximation and parameterized algorithms for covering disjointness-compliable set families
by: Nutov, Zeev, et al.
Published: (2025)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
by: Bergougnoux, Benjamin, et al.
Published: (2026)

Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
by: Bojikian, Narek, et al.
Published: (2025)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
by: Bojikian, Narek, et al.
Published: (2024)

A faster algorithm for the construction of optimal factoring automata
by: Erlebach, Thomas, et al.
Published: (2024)

A faster heuristic for the Traveling Salesman Problem with Drone
by: Hokama, Pedro H. D. B., et al.
Published: (2024)

New algorithms for girth and cycle detection
by: Roditty, Liam, et al.
Published: (2025)

An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
by: Mitosek, Piotr, et al.
Published: (2024)

Engineering faster double-array Aho-Corasick automata
by: Kanda, Shunsuke, et al.
Published: (2022)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Coloring for dispersion: A polynomial-time algorithm for cardinality-constrained 2-anticlustering
by: Tran, Nguyen Khoa, et al.
Published: (2026)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
by: Bojikian, Narek, et al.
Published: (2025)

Improved algorithms for learning quantum Hamiltonians, via flat polynomials
by: Narayanan, Shyam
Published: (2024)

A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data
by: Smart, Bridget, et al.
Published: (2025)

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
by: Grigoriev, Alexander, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

Improved approximation algorithms for the EPR Hamiltonian
by: Ju, Nathan, et al.
Published: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
by: Chen, Tyler, et al.
Published: (2025)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

The S-Hamiltonian Cycle Problem
by: Amarilli, Antoine, et al.
Published: (2026)

Finding longer cycles via shortest colourful cycle
by: Björklund, Andreas, et al.
Published: (2024)

Better space-time-robustness trade-offs for set reconciliation
by: Belazzougui, Djamal, et al.
Published: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

A square root algorithm faster than Newton's method for multiprecision numbers, using floating-point arithmetic
by: Romano, Fabio
Published: (2024)