UNSPECIFIED (2000) A dynamic algorithm for maintaining graph partitions. In: 7th Scandinavian Workshop on Algorithm Theory (SWAT 2000), JUL 05-07, 2000, BERGEN, NORWAY.

Full text not available from this repository.

Abstract

We propose an algorithm for maintaining a partition of dynamic planar graphs motivated by applications in load balancing for solving partial differential equations on a shared memory multiprocessor. We consider planar graphs of bounded face sizes that can be modified by local insertions or deletions of vertices or edges so that planarity is preserved. In our paper we describe a data structure that can be updated in O(log n) time after any such modification of the graph, where n is the current size of the graph, and allows an almost optimal partition of a required size to be maintained. More precisely, the size of the separator is within an O(n(delta)) factor of the optimal for the class of planar graphs, where delta is any positive constant, and can be listed in time proportional to its size. The dynamic data structure occupies O(n) space and can initially be constructed in time linear to the size of the original graph.

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 THEORY - SWAT 2000
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-67690-2
ISSN:	0302-9743
Editor:	Halldorsson, MM
Date:	2000
Volume:	1851
Number of Pages:	12
Page Range:	pp. 71-82
Publication Status:	Published
Title of Event:	7th Scandinavian Workshop on Algorithm Theory (SWAT 2000)
Location of Event:	BERGEN, NORWAY
Date(s) of Event:	JUL 05-07, 2000
URI:	http://wrap.warwick.ac.uk/id/eprint/12780

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item