Packing directed circuits fractionally (Q1894706): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: P. D. Seymour / rank | |||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Property / author | |||
Property / author: P. D. Seymour / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramanujan graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:53, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing directed circuits fractionally |
scientific article |
Statements
Packing directed circuits fractionally (English)
0 references
26 November 1995
0 references
A fractional circuit packing of value \(v\) of a directed graph \(G\) is a function that assigns a non-negative rational number \(q(C)\) to each circuit \(C\) such that (i) the sum of \(q(C)\) over all circuits containing any given vertex is at most one, and (ii) the sum of \(q(C)\) over all circuits is \(v\). The author shows that if every fractional circuit packing of \(G\) has value at most \(k\) where \(k\geq 1\), then there exists a set of at most \(4k\log(4k) \log\log_2(4k)\) vertices of \(G\) that meets every circuit.
0 references
directed circuits
0 references
fractional circuit packing
0 references
directed graph
0 references