Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Cooperative guards in art galleries

100%

Żyliński P.

Instytut Matematyczny Polskiej Akademii Nauk

The art gallery problem was originally posed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon. The guard is assumed to be a stationary point which can see any other point that can be connected to it by a line segment within the art gallery. The first result is due to Chvátal (1975), who proved that ⌊n/3⌋ guards are occasionally necessary and always sufficient to cover a polygon with n vertices. Since then many different variations of this problem have arisen, and in this dissertation, we investigate the cooperative guards problem posed by Liaw, Huang and Lee in 1993. In general, two variants of the cooperation are distinguished: a guard set is said to be cooperative provided that for any guard, if something goes wrong with him, all the others can be informed (by using the line-of-sight communication only), and k-guarded if each guard is seen by at least k of its colleagues. We present tight bounds for various classes of galleries (arbitrary, orthogonal, monotone, spiral, star-shaped, with holes) as well as we discuss the complexity of the problem of determining the minimum number of cooperative (resp. k-guarded) guards sufficient to cover an art gallery. Finally, we investigate the cooperative guards problem in fortresses and grids.

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

Equitable coloring of Kneser graphs

49%

Fidytek R., Furmańczyk H., Żyliński P.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 1

119-142

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k) are discussed.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

2 Żyliński P.

1 Fidytek R.

1 Furmańczyk H.

1 2009

1 2007

Wyniki wyszukiwania

Cooperative guards in art galleries

Equitable coloring of Kneser graphs