Finding detours is fixed-parameter tractable

DOI10.4230/LIPICS.ICALP.2017.54zbMATH Open1441.68104MaRDI QIDQ5111385FDOQ5111385

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

Publication date: 27 May 2020

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

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)

Cited In (7)

• Long directed detours: reduction to 2-disjoint paths
• Faster deterministic parameterized algorithm for \(k\)-path
• The tree longest detour problem in a biconnected graph.
• Title not available (Why is that?)
• Basic Terminology, Notation and Results
• Detours in directed graphs
• 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)