Finding detours is fixed-parameter tractable

DOI10.4230/LIPICS.ICALP.2017.54MaRDI QIDQ5111385zbMATH OpenFDO

Authors Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin

Publication date 27 May 2020

zbMATH Keywords

graph minorslongest pathfixed-parameter tractable algorithmsabove-guarantee parameterization

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Finding detours is fixed-parameter tractable
• Long directed \((s,t)\)-path: FPT algorithm
• The tree longest detour problem in a biconnected graph.
• scientific article; zbMATH DE number 3974318
• Finding Long Paths, Cycles and Circuits

Cited in

(10)

• Long directed detours: reduction to 2-disjoint paths
• The tree longest detour problem in a biconnected graph.
• Faster deterministic parameterized algorithm for k-path
• scientific article; zbMATH DE number 7525484 (Why is no real title available?)
• Basic Terminology, Notation and Results
• Detours in directed graphs
• Longest cycle above Erdős-Gallai bound
• Long directed \((s,t)\)-path: FPT algorithm
• Finding detours is fixed-parameter tractable
• Longest cycle above Erdős-Gallai bound

This page was built for publication: Finding detours is fixed-parameter tractable

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