The Library
Partitioning planar graphs with costs and weights
Tools
UNSPECIFIED (2002) Partitioning planar graphs with costs and weights. In: 4th International Workshop on Algorithm Engineering and Experiments, SAN FRANCISCO, CALIFORNIA, JAN 04-05, 2002. Published in: ALGORITHM ENGINEERING AND EXPERIMENTS, 2409 pp. 98-110. ISBN 3-540-43977-3. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up their implementation and improve the partition quality. In particular, we consider planar graphs with costs and weights on the vertices, where weights are used to estimate the sizes of the components and costs are used to estimate the size of the separator. We show that one can find a small separator that divides the graph into components of bounded size. We describe implementations of the partitioning algorithms and discuss results of our experiments.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | ALGORITHM ENGINEERING AND EXPERIMENTS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-43977-3 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Mount, DM and Stein, C | ||||
Official Date: | 2002 | ||||
Dates: |
|
||||
Volume: | 2409 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 98-110 | ||||
Publication Status: | Published | ||||
Title of Event: | 4th International Workshop on Algorithm Engineering and Experiments | ||||
Location of Event: | SAN FRANCISCO, CALIFORNIA | ||||
Date(s) of Event: | JAN 04-05, 2002 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |