On Efficient Construction of Minimum-Sum Vertex Covers
Loading...
Authors
Rasmussen, Craig W.
Subjects
Advisors
Date of Issue
2006-11-30
Date
Publisher
Language
Abstract
Let G = ( V, E) be a simple graph. A vertex labeling is a bijection f: V → { l, 2, ... ,!VI}. The
weight w(e) of an edge e = uv ∈E is given by w(e) = min{f(u), f(v)}. The minimum-sum ver~ex
cover is a vertex labeling that minimizes ∑ₑ∈ ᴇ ʷ(ͤ) . The minimum such sum is called the min~mum-sum
vertex cover cost, denoted by µ (G). The problem of determining µs (G) is NP-complete
m the general case, however, we show that minimum-sum vertex covers of split graphs and caterpillars
can be computed in polynomial time.
Type
Article
Description
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
9 p.
Citation
Rasmussen, Craig. "On Efficient Construction of Minimum-sum Vertex Covers." Graph Theory Notes of New York LII (2007): New York Academy of Sciences. 51-59.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.