A multivariate framework for weighted FPT algorithms
From MaRDI portal
Publication:2402359
DOI10.1016/J.JCSS.2017.05.003zbMath1372.68145arXiv1407.2033OpenAlexW2963396431MaRDI QIDQ2402359
Publication date: 7 September 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.2033
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
A Multivariate Approach for Weighted FPT Algorithms ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Kernels for packing and covering problems ⋮ Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs ⋮ Parameterized approximation algorithms for weighted vertex cover ⋮ Parameterized approximation algorithms for weighted vertex cover
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Parameterized edge dominating set in graphs with degree bounded by 3
- New parameterized algorithms for the edge dominating set problem
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Improved upper bounds for vertex cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- An efficient fixed-parameter algorithm for 3-hitting set
- Representative families: a unified tradeoff-based approach
- Improved algorithms for feedback vertex set problems
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- On two techniques of combining branching and treewidth
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Approximating the maximum internal spanning tree problem
- Minimum leaf out-branching and related problems
- A linear vertex kernel for maximum internal spanning tree
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Exact algorithms for edge domination
- Algorithms for topology-free and alignment network queries
- Fixed-parameter tractability results for feedback set problems in tournaments
- Sharp separation and applications to exact and parameterized algorithms
- Crown reductions for the minimum weighted vertex cover problem
- Vertex Cover: Further Observations and Further Improvements
- Algorithms for k-Internal Out-Branching
- Deterministic Parameterized Connected Vertex Cover
- Enumerate and Measure: Improving Parameter Budget Management
- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
- Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Faster Algebraic Algorithms for Path and Packing Problems
- A Note on Vertex Cover in Graphs with Maximum Degree 3
- Limits and Applications of Group Algebras for Parameterized Problems
- Algorithms for maximum independent sets
- Nondeterminism within $P^ * $
- Color-coding
- On efficient fixed-parameter algorithms for weighted vertex cover
- Minimum bisection is fixed parameter tractable
- Determinant Sums for Undirected Hamiltonicity
- Branching and Treewidth Based Exact Algorithms
This page was built for publication: A multivariate framework for weighted FPT algorithms
