CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Powers of geometric intersection graphs and dispersion algorithms

Geir Agnarsson ; Peter Damaschke (Institutionen för datavetenskap, Algoritmer) ; Magnus Halldorsson
Discrete Applied Mathematics (0166-218X). Vol. 132 (2003), 1-3, p. 3-16.
[Artikel, refereegranskad vetenskaplig]

We study powers of certain geometric intersection graphs: interval graphs, m-trapezoid graphs and circular-arc graphs. We define the pseudo product of two graphs on the same set of vertices, and show that it is contained in one of the three classes of graphs mentioned here above, if both factors are also in that class and fulfill certain conditions. This gives a new proof of the fact that these classes are closed under taking power; more importantly, we get efficient methods for computing the representation for the k-th power (k integer) of a graph that belongs to one of these classes, with a given representation sorted by endpoints. We then use these results to give efficient algorithms for the k-independent set, dispersion and weighted dispersion problem on these classes of graphs, provided that their geometric representations are given. (Abstract slightly adapted from the paper.)

Nyckelord: powers of graphs, intersection graphs, interval graphs, circular-arc graphs, trapezoid graphs, dispersion

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1692


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur