Exact algorithms and applications for tree-like Weighted Set Cover
From MaRDI portal
Publication:866547
DOI10.1016/j.jda.2005.07.005zbMath1110.68173OpenAlexW2132377873MaRDI QIDQ866547
Publication date: 14 February 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2005.07.005
NP-hard problemsfixed-parameter tractabilitymulticut in treesMinimum Weighted Edge Cover on acyclic hypergraphsWeighted Set Cover
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) General biology and biomathematics (92B05)
Related Items (15)
A dynamic programming algorithm for tree-like weighted set packing problem ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Static and dynamic source locations in undirected networks ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ Hardness and algorithms for electoral manipulation under media influence ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ Parameterized algorithms for weighted matching and packing problems ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion ⋮ Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Refined memorization for vertex cover
- Optimization, approximation, and complexity classes
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- A threshold of ln n for approximating set cover
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- Fixed-parameter tractability and data reduction for multicut in trees
- Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Graph minors. II. Algorithmic aspects of tree-width
- An Almost Linear-Time Algorithm for Graph Realization
- Optimal Capacity Scheduling—I
- Approximating k-set cover and complementary graph coloring
- Practical algorithms on partial k-trees with an application to domination-like problems
- Mathematical Foundations of Computer Science 2004
- Algorithms – ESA 2004
- Algorithms and Data Structures
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Exact algorithms and applications for tree-like Weighted Set Cover
