### Skapa referens, olika format (klipp och klistra)

**Harvard**

Agnarsson, G., Damaschke, P. och Halldórsson, M. (2002) *Powers of geometric intersection graphs and dispersion algorithms*.

** BibTeX **

@conference{

Agnarsson2002,

author={Agnarsson, G. and Damaschke, Peter and Halldórsson, M.},

title={Powers of geometric intersection graphs and dispersion algorithms},

booktitle={Lecture Notes in Computer Science. 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002},

isbn={978-3-540-43866-3},

pages={140-149},

abstract={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.},

year={2002},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 170519

A1 Agnarsson, G.

A1 Damaschke, Peter

A1 Halldórsson, M.

T1 Powers of geometric intersection graphs and dispersion algorithms

YR 2002

T2 Lecture Notes in Computer Science. 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002

SN 978-3-540-43866-3

SP 140

OP 149

AB 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.

LA eng

DO 10.1007/3-540-45471-3_15

LK http://dx.doi.org/10.1007/3-540-45471-3_15

OL 30