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

Powers of geometric intersection graphs and dispersion algorithms

G. Agnarsson ; Peter Damaschke (Institutionen för datavetenskap) ; M. Halldórsson
Lecture Notes in Computer Science. 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002 (0302-9743). Vol. 2368 (2002), p. 140-149.
[Konferensbidrag, refereegranskat]

We study powers of certain geometric intersection graphs: interval graphs, m-trapezoid graphs and circular-arc graphs. We define the pseudo product, (G,G′) → G * G′, of two graphs G and G′ on the same set of vertices, and show that G*G′ is contained in one of the three classes of graphs mentioned here above, if both G and G′ 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 G k if k ≥ 1 is an integer and G 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.



Denna post skapades 2013-01-14. Senast ändrad 2015-02-11.
CPL Pubid: 170519

 

Läs direkt!


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


Institutioner (Chalmers)

Institutionen för datavetenskap (2002-2004)

Ämnesområden

Data- och informationsvetenskap

Chalmers infrastruktur