Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

Packing feedback vertex sets in tournaments
by
Xujin Chen
CAS & LSU
Coauthors: Xiaodong Hu and Wenan Zang

We present a structural characterization of all tournaments T = (V, A) such that, for any nonnegative integral weight function defined on V, the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. Our constructive proof leads to exact and approximation algorithms for the feedback vertex set packing problem on tournaments.

We also answer a question of Frank by showing that it is NP-complete to decide whether each vertex of a given digraph can be colored by red or blue such that no cycle is monochromatic.

Date received: April 12, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-34.