Exact algorithms and applications for tree-like Weighted Set Cover
DOI10.1016/J.JDA.2005.07.005zbMATH Open1110.68173OpenAlexW2132377873MaRDI QIDQ866547FDOQ866547
Authors: Jiong Guo, Rolf Niedermeier 
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
Recommendations
- On efficient fixed-parameter algorithms for weighted vertex cover
- A multivariate approach for weighted FPT algorithms
- Two fixed-parameter algorithms for vertex covering by paths on trees
- Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
- Approximating the minmax rooted-tree cover in a tree
fixed-parameter tractabilityNP-hard problemsmulticut in treesMinimum Weighted Edge Cover on acyclic hypergraphsWeighted Set Cover
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) General biology and biomathematics (92B05)
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- Title not available (Why is that?)
- A partial k-arboretum of graphs with bounded treewidth
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Treewidth. Computations and approximations
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter tractability and data reduction for multicut in trees
- Graph-Theoretic Concepts in Computer Science
- Practical algorithms on partial k-trees with an application to domination-like problems
- Optimal Capacity Scheduling—I
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Refined memorization for vertex cover
- An Almost Linear-Time Algorithm for Graph Realization
- Algorithms and Data Structures
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Approximating \(k\)-set cover and complementary graph coloring
- Algorithms – ESA 2004
- Mathematical Foundations of Computer Science 2004
- Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
Cited In (21)
- Parameterized algorithms for weighted matching and packing problems
- Parameterized complexity of weighted multicut in trees
- Parameterized complexity of multicut in weighted trees
- The complexity of weighted counting for acyclic conjunctive queries
- Title not available (Why is that?)
- An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
- Tree decompositions of graphs: saving memory in dynamic programming
- Title not available (Why is that?)
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
- Hardness and algorithms for electoral manipulation under media influence
- Computing cooperative solution concepts in coalitional skill games
- Static and dynamic source locations in undirected networks
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Set cover, set packing and hitting set for tree convex and tree-like set systems
- A multivariate approach for weighted FPT algorithms
- Weighted target set selection on trees and cycles
- Efficient computation of tolerances in the weighted independent set problem for trees
- Preferences single-peaked on a tree: multiwinner elections and structural results
- A dynamic programming algorithm for tree-like weighted set packing problem
This page was built for publication: Exact algorithms and applications for tree-like Weighted Set Cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866547)
