A Linear-Time Parameterized Algorithm for Node Unique Label Cover
From MaRDI portal
Publication:5111746
DOI10.4230/LIPIcs.ESA.2017.57zbMath1442.68288arXiv1604.08764OpenAlexW2963262002MaRDI QIDQ5111746
Saket Saurabh, Daniel Lokshtanov, M. S. Ramanujan
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1604.08764
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- FPT algorithms for path-transversal and cycle-transversal problems
- Graph minors. XX: Wagner's conjecture
- Parameterized graph separation problems
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- Which problems have strongly exponential complexity?
- Computing crossing numbers in quadratic time
- Graph minors. XIII: The disjoint paths problem
- An improved parameterized algorithm for the minimum node multiway cut problem
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Half-integrality, LP-branching, and FPT Algorithms
- On Multiway Cut Parameterized above Lower Bounds
- Planar Subgraph Isomorphism Revisited
- A Faster Parameterized Algorithm for Group Feedback Edge Set
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
- On the power of unique 2-prover 1-round games
- Nonconstructive tools for proving polynomial-time decidability
- Faster Parameterized Algorithms Using Linear Programming
- Planarity Allowing Few Error Vertices in Linear Time
- Computing crossing numbers in quadratic time
- A linear time algorithm for finding tree-decompositions of small treewidth
- Solving d-SAT via Backdoors to Small Treewidth
- Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Linear-Time FPT Algorithms via Network Flow
- Half-integrality, LP-branching and FPT Algorithms
- A Near-Optimal Planarization Algorithm
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
This page was built for publication: A Linear-Time Parameterized Algorithm for Node Unique Label Cover