Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
From MaRDI portal
Publication:897878
DOI10.1016/j.tcs.2015.09.023zbMath1331.68281arXiv1411.2680OpenAlexW2513955757MaRDI QIDQ897878
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.2680
Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
Scale reduction techniques for computing maximum induced bicliques ⋮ Finding near-optimal independent sets at scale ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Research trends in combinatorial optimization ⋮ A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ A probabilistic algorithm for vertex cover ⋮ Maximum independent sets and supervised learning ⋮ Unnamed Item ⋮ Solving vertex cover in polynomial time on hyperbolic random graphs ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Finding odd cycle transversals.
- Improved upper bounds for vertex cover
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Fast algorithms for max independent set
- Exact Algorithms for Maximum Independent Set
- On Multiway Cut Parameterized above Lower Bounds
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- A measure & conquer approach for the analysis of exact algorithms
- Algorithm Engineering for Optimal Graph Bipartization
- Vertex packings: Structural properties and algorithms
- Faster Parameterized Algorithms Using Linear Programming
- Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
- Linear-Time FPT Algorithms via Network Flow
- Half-integrality, LP-branching and FPT Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
