On feedback vertex sets in tournaments

S. Gaspers; M. Mnich

On feedback vertex sets in tournaments

S. Gaspers, M. Mnich

Combinatorische Optimalisering - EIDMA

Onderzoeksoutput: Boek/rapport › Rapport › Academic

Samenvatting

A tournament T is an orientation of a complete graph, and a feedback vertex set of T is a subset of vertices intersecting every directed cycle of T. We prove that every tournament on n vertices has at most 1:6740n minimal feedback vertex sets and some tournaments have 1:5448n minimal feedback vertex sets. This improves a result by Moon (1971) who showed upper and lower bounds of 1:7170n and 1:4757n on the maximum number of minimal feedback vertex sets in tournaments.

Originele taal-2	Engels
Uitgeverij	s.n.
Aantal pagina's	18
Status	Gepubliceerd - 2009

Publicatie series

Naam	arXiv.org [cs.DM]
Volume	0905.0567

Vingerafdruk Duik in de onderzoeksthema's van 'On feedback vertex sets in tournaments'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@book{7c23b58949d9441fbbc10df1fd320619,

title = "On feedback vertex sets in tournaments",

abstract = "A tournament T is an orientation of a complete graph, and a feedback vertex set of T is a subset of vertices intersecting every directed cycle of T. We prove that every tournament on n vertices has at most 1:6740n minimal feedback vertex sets and some tournaments have 1:5448n minimal feedback vertex sets. This improves a result by Moon (1971) who showed upper and lower bounds of 1:7170n and 1:4757n on the maximum number of minimal feedback vertex sets in tournaments.",

author = "S. Gaspers and M. Mnich",

year = "2009",

language = "English",

series = "arXiv.org [cs.DM]",

publisher = "s.n.",

}

TY - BOOK

T1 - On feedback vertex sets in tournaments

AU - Gaspers, S.

AU - Mnich, M.

PY - 2009

Y1 - 2009

N2 - A tournament T is an orientation of a complete graph, and a feedback vertex set of T is a subset of vertices intersecting every directed cycle of T. We prove that every tournament on n vertices has at most 1:6740n minimal feedback vertex sets and some tournaments have 1:5448n minimal feedback vertex sets. This improves a result by Moon (1971) who showed upper and lower bounds of 1:7170n and 1:4757n on the maximum number of minimal feedback vertex sets in tournaments.

AB - A tournament T is an orientation of a complete graph, and a feedback vertex set of T is a subset of vertices intersecting every directed cycle of T. We prove that every tournament on n vertices has at most 1:6740n minimal feedback vertex sets and some tournaments have 1:5448n minimal feedback vertex sets. This improves a result by Moon (1971) who showed upper and lower bounds of 1:7170n and 1:4757n on the maximum number of minimal feedback vertex sets in tournaments.

M3 - Report

T3 - arXiv.org [cs.DM]

BT - On feedback vertex sets in tournaments

PB - s.n.

ER -