Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: tournaments

Sortuj według:

Ogranicz wyniki do:

Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

100%

Dutta K., Subramanian C. R.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 3

467-495

Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance of w(n)/(ln n) (for any sufficiently slow w(n) → ∞) from an integer, then mat(D) is ⌊2(logrn) + 1⌋ a.a.s. As a consequence, it is shown that mat(D) is 1-point concentrated for all n belonging to a subset of positive integers of density 1 if p is independent of n. It is also shown that there are functions p = p(n) for which mat(D) is provably not concentrated in a single value. We also establish thresholds (on p) for the existence of induced acyclic tournaments of size i which are sharp for i = i(n) → ∞. We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least logrn + Θ(√logrn). Our results are valid as long as p ≥ 1/n. All of these results also carry over (with some slight changes) to a related model which allows 2-cycles

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Dichromatic number, circulant tournaments and Zykov sums of digraphs

86%

Neumann-Lara V.

Discussiones Mathematicae Graph Theory

2000

tom 20

nr 2

197-207

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Dutta K.

1 Neumann-Lara V.

1 Subramanian C. R.

1 2014

1 2000

Wyniki wyszukiwania

Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

Dichromatic number, circulant tournaments and Zykov sums of digraphs