Exact algorithms and applications for tree-like Weighted Set Cover

DOI10.1016/J.JDA.2005.07.005zbMath1110.68173OpenAlexW2132377873MaRDI QIDQ866547

Rolf Niedermeier, Jiong Guo

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

zbMATH Keywords

NP-hard problemsfixed-parameter tractabilitymulticut in treesMinimum Weighted Edge Cover on acyclic hypergraphsWeighted Set Cover

Mathematics Subject Classification ID

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