Results on the Min-Sum Vertex Cover Problem

Abstract

Let G be a graph with the vertex set V (G), edge set E(G). A vertex labeling is a bijection f : V (G) - {1, 2, . . . , |V (G)|}. The weight of e = uv 2 E(G) is given by g(e) = min{f(u), f(v)}. The min-sum vertex cover (msvc) is a vertex labeling that minimizes the vertex cover number mu(s)(G) = Sigma(eEpsilonE(G) g(e). The minimum such sum is called the msvc cost. In this paper, we give both general bounds and exact results for the msvc cost on several classes of graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA573102

Entities

People

  • Craig Rasmussen
  • Pantelimon Stanica
  • Ralucca Gera
  • Steve Horton

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Equations
  • Inequalities
  • Information Operations
  • Mathematics
  • Notation
  • Observation
  • Schools
  • Sharpness
  • United States
  • United States Military Academy

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Life Cycle Cost Analysis