The maximum vertex coverage problem on bipartite graphs
From MaRDI portal
Publication:2448919
DOI10.1016/j.dam.2013.05.015zbMath1288.05201OpenAlexW2049200290MaRDI QIDQ2448919
Bruno Simeone, Nicola Apollonio
Publication date: 5 May 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.05.015
Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Indiscernibility structures induced from function sets : Graph and digraph case ⋮ Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Simplicial complexes and closure systems induced by indistinguishability relations ⋮ Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7 ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Maximum Weighted Independent Sets with a Budget ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ Blocking unions of arborescences ⋮ The complexity of mixed-connectivity ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum \(h\)-colourable subgraph problem in balanced graphs
- A min-max relation for the partial q-colourings of a graph. II: Box perfection
- \((p,k)\)-coloring problems in line graphs
- Minmax relations for cyclically ordered digraphs
- Characterizations of strongly chordal graphs
- Clustering and domination in perfect graphs
- Matching theory
- The maximum k-colorable subgraph problem for chordal graphs
- On chain and antichain families of a partially ordered set
- Geometric algorithms and combinatorial optimization
- The complexity of generalized clique covering
- Minimax relations for the partial q-colorings of a graph
- On approximation of max-vertex-cover
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Recognizing Helly edge-path-tree graphs and their clique graphs
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Improved approximation of maximum vertex cover
- Combinatorial Optimization
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Minconvex Factors of Prescribed Size in Graphs
- Algorithms for maximumk-colorings andk-coverings of transitive graphs
- Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Graph Classes: A Survey
- A Unified Approach to Approximating Partial Covering Problems
- Integer Programming and Combinatorial Optimization
