Advertisement
Published in:
2005 | OriginalPaper | Chapter
A Min-Max Relation on Packing Feedback Vertex Sets
Authors : Xujin Chen, Guoli Ding, Xiaodong Hu, Wenan Zang
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
G
be a graph with a nonnegative integral function
w
defined on
V
(
G
). A family
$\mathcal{F}$
of subsets of
V
(
G
) (repetition is allowed) is called a
feedback vertex set packing
in
G
if the removal of any member of
$\mathcal{F}$
from
G
leaves a forest, and every vertex
v
∈
V
(
G
) is contained in at most
w
(
v
) members of
$\mathcal{F}$
. The
weight
of a cycle
C
in
G
is the sum of
w
(
v
), over all vertices
v
of
C
. In this paper we characterize all graphs with the property that, for any nonnegative integral function
w
, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle.