Going Far from Degeneracy
From MaRDI portal
Publication:5130907
DOI10.1137/19M1290577zbMath1451.05229arXiv1902.02526OpenAlexW2978838090WikidataQ130352428 ScholiaQ130352428MaRDI QIDQ5130907
Fahad Panolan, Meirav Zehavi, Fedor V. Fomin, Saket Saurabh, Petr A. Golovach, Daniel Lokshtanov
Publication date: 29 October 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.02526
Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Detours in directed graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A randomized algorithm for long directed cycle
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Vertex cover problem parameterized above and below tight bounds
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Parameterizing above or below guaranteed values
- Long directed \((s,t)\)-path: FPT algorithm
- Faster deterministic parameterized algorithm for \(k\)-path
- Narrow sieves for parameterized paths and packings
- The linear arrangement problem parameterized above guaranteed value
- Polynomial Kernels for {\lambda}-extendible Properties Parameterized Above the Poljak-Turz\'ik Bound
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- On maximal paths and circuits of graphs
- Faster Algebraic Algorithms for Path and Packing Problems
- Divide-and-Color
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- Smallest-last ordering and clustering and graph coloring algorithms
- A Characterization of Block-Graphs
- On Linear Time Minor Tests with Depth-First Search
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Color-coding
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- Problems remaining NP-complette for sparse or dense graphs
- Faster Parameterized Algorithms Using Linear Programming
- Finding a long directed cycle
- Finding Detours is Fixed-Parameter Tractable
- Parameterized Algorithms
- Parameterized Traveling Salesman Problem: Beating the Average
- Some Theorems on Abstract Graphs
This page was built for publication: Going Far from Degeneracy
