Packing directed circuits fractionally

P. D. Seymour

doi:10.1007/BF01200760

Packing directed circuits fractionally

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

165 Scopus citations

Abstract

Let G be a digraph, and let k≥1, such that no "fractional" packing of directed circuits of G has value >k, when every vertex is given "capacity" 1. We prove there is a set of O (k log k log k) vertices meeting all directed circuits of G.

Original language	English (US)
Pages (from-to)	281-288
Number of pages	8
Journal	Combinatorica
Volume	15
Issue number	2
DOIs	https://doi.org/10.1007/BF01200760
State	Published - Jun 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computational Mathematics
Discrete Mathematics and Combinatorics

Keywords

Mathematics Subject Classification (1991): 05C20, 05C38, 05C70

Access to Document

10.1007/BF01200760

Cite this

@article{a269eef21e494985ae32d7695f7ebcc4,

title = "Packing directed circuits fractionally",

abstract = "Let G be a digraph, and let k≥1, such that no {"}fractional{"} packing of directed circuits of G has value >k, when every vertex is given {"}capacity{"} 1. We prove there is a set of O (k log k log k) vertices meeting all directed circuits of G.",

keywords = "Mathematics Subject Classification (1991): 05C20, 05C38, 05C70",

author = "Seymour, {P. D.}",

year = "1995",

month = jun,

doi = "10.1007/BF01200760",

language = "English (US)",

volume = "15",

pages = "281--288",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Packing directed circuits fractionally

AU - Seymour, P. D.

PY - 1995/6

Y1 - 1995/6

N2 - Let G be a digraph, and let k≥1, such that no "fractional" packing of directed circuits of G has value >k, when every vertex is given "capacity" 1. We prove there is a set of O (k log k log k) vertices meeting all directed circuits of G.

AB - Let G be a digraph, and let k≥1, such that no "fractional" packing of directed circuits of G has value >k, when every vertex is given "capacity" 1. We prove there is a set of O (k log k log k) vertices meeting all directed circuits of G.

KW - Mathematics Subject Classification (1991): 05C20, 05C38, 05C70

UR - http://www.scopus.com/inward/record.url?scp=34249756824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249756824&partnerID=8YFLogxK

U2 - 10.1007/BF01200760

DO - 10.1007/BF01200760

M3 - Article

AN - SCOPUS:34249756824

SN - 0209-9683

VL - 15

SP - 281

EP - 288

JO - Combinatorica

JF - Combinatorica

IS - 2

ER -

Packing directed circuits fractionally

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this