A Linear-Time Parameterized Algorithm for Node Unique Label Cover

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

zbMATH Keywords

data structuresfixed-parameter tractabilityunique label coverlinear-time FPT algorithms

Mathematics Subject Classification ID

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