Going far from degeneracy

DOI10.4230/LIPICS.ESA.2019.47MaRDI QIDQ5075790zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

Publication date 11 May 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2019.47

zbMATH Keywords

above guarantee parameterizationfixed-parameter tractabilitylongest cyclelongest path

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Going far from degeneracy
• Longest cycle above Erdős-Gallai bound
• Computing and Combinatorics
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Finding Long Paths, Cycles and Circuits

Cites work

• A Characterization of Block-Graphs
• A randomized algorithm for long directed cycle
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Divide-and-Color
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Faster Algebraic Algorithms for Path and Packing Problems
• Faster deterministic parameterized algorithm for k-path
• Faster parameterized algorithms using linear programming
• Finding a long directed cycle
• Finding detours is fixed-parameter tractable
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• Improved algorithms for path, matching, and packing problems
• Long directed \((s,t)\)-path: FPT algorithm
• On Linear Time Minor Tests with Depth-First Search
• On maximal paths and circuits of graphs
• Parameterized algorithms
• Parameterized traveling salesman problem: beating the average
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Polynomial kernels for -extendible properties parameterized above the Poljak-Turzík bound
• Problems remaining NP-complette for sparse or dense graphs
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Smallest-last ordering and clustering and graph coloring algorithms
• Some Theorems on Abstract Graphs
• The linear arrangement problem parameterized above guaranteed value
• Vertex cover problem parameterized above and below tight bounds

Cited in

(3)

• Degeneracy: Resolve or Avoid?
• Sparse graphs without long induced paths
• Longest cycle above Erdős-Gallai bound

This page was built for publication: Going far from degeneracy

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