The generalized vertex cover problem and some variations

DOI10.1016/j.disopt.2018.06.004zbMath1454.90031arXiv1708.03703OpenAlexW2963727291WikidataQ129588415 ScholiaQ129588415MaRDI QIDQ1756348

Pooja Pandey, Abraham P. Punnen

Publication date: 14 January 2019

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.03703

zbMATH Keywords

complexityalgorithmsquadratic programming0-1 programminggeneralized vertex cover

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Introduction to QUBO ⋮ Complexity and Polynomially Solvable Special Cases of QUBO

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• The unconstrained binary quadratic programming problem: a survey
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Exact solutions to generalized vertex covering problems: a comparison of two models
• Relaxations of vertex packing
• A solvable case of quadratic 0-1 programming
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Structure preserving reductions among convex optimization problems
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• An effective modeling and solution approach for the generalized independent set problem
• The minimum generalized vertex cover problem
• Polynomially Solvable Cases of Binary Quadratic Programs
• An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Minimum cuts and related problems
• Approximation algorithms for NP-complete problems on planar graphs
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Efficient Computation of the Binary Vector That Maximizes a Rank-Deficient Quadratic Form
• A Graph-Theoretic Equivalence for Integer Programs
• A polynomial case of unconstrained zero-one quadratic optimization

This page was built for publication: The generalized vertex cover problem and some variations