The maximum vertex coverage problem on bipartite graphs

DOI10.1016/J.DAM.2013.05.015zbMATH Open1288.05201OpenAlexW2049200290MaRDI QIDQ2448919FDOQ2448919

Authors: Nicola Apollonio, Bruno Simeone 

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

Recommendations

• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• Polynomially solvable cases of the minimum biclique vertex-cover problem

zbMATH Keywords

matchinghypergraphsNP-hardnessvertex covertransversal numberclique covering

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Geometric algorithms and combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Classes: A Survey
• Clustering and domination in perfect graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing Helly edge-path-tree graphs and their clique graphs
• A characterization of perfect graphs
• Title not available (Why is that?)
• Minconvex Factors of Prescribed Size in Graphs
• Title not available (Why is that?)
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Title not available (Why is that?)
• Characterizations of strongly chordal graphs
• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• The maximum k-colorable subgraph problem for chordal graphs
• The complexity of generalized clique covering
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• Combinatorial optimization. Packing and covering
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• On chain and antichain families of a partially ordered set
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Minmax relations for cyclically ordered digraphs
• Title not available (Why is that?)
• On approximation of max-vertex-cover
• Integer Programming and Combinatorial Optimization
• Title not available (Why is that?)
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
• A Unified Approach to Approximating Partial Covering Problems
• Minimax relations for the partial q-colorings of a graph
• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• \((p,k)\)-coloring problems in line graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved approximation of maximum vertex cover

Cited In (22)

• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
• Indiscernibility structures induced from function sets: graph and digraph case
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• Computing densest \(k\)-subgraph with structural parameters
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Blocking unions of arborescences
• Maximum weighted independent sets with a budget
• The generalized vertex cover problem and some variations
• The most vital nodes with respect to independent set and vertex cover
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
• Simplicial complexes and closure systems induced by indistinguishability relations
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
• The complexity of mixed-connectivity
• Maximizing coverage while ensuring fairness: a tale of conflicting objectives
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

This page was built for publication: The maximum vertex coverage problem on bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448919)