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

**Harvard**

Agnarsson, G., Damaschke, P. och Halldorsson, M. (2003) *Powers of geometric intersection graphs and dispersion algorithms*.

** BibTeX **

@article{

Agnarsson2003,

author={Agnarsson, Geir and Damaschke, Peter and Halldorsson, Magnus},

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

journal={Discrete Applied Mathematics},

issn={0166-218X},

volume={132},

issue={1-3},

pages={3-16},

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

year={2003},

keywords={powers of graphs, intersection graphs, interval graphs, circular-arc graphs, trapezoid graphs, dispersion},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 1692

A1 Agnarsson, Geir

A1 Damaschke, Peter

A1 Halldorsson, Magnus

T1 Powers of geometric intersection graphs and dispersion algorithms

YR 2003

JF Discrete Applied Mathematics

SN 0166-218X

VO 132

IS 1-3

SP 3

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

LA eng

DO 10.1016/S0166-218X(03)00386-X

LK http://dx.doi.org/10.1016/S0166-218X(03)00386-X

OL 30