A dynamic algorithm for maintaining graph partitions
UNSPECIFIED (2000) A dynamic algorithm for maintaining graph partitions. In: 7th Scandinavian Workshop on Algorithm Theory (SWAT 2000), BERGEN, NORWAY, JUL 05-07, 2000. Published in: ALGORITHM THEORY - SWAT 2000, 1851 pp. 71-82.Full text not available from this repository.
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|
|Number of Pages:||12|
|Page Range:||pp. 71-82|
|Title of Event:||7th Scandinavian Workshop on Algorithm Theory (SWAT 2000)|
|Location of Event:||BERGEN, NORWAY|
|Date(s) of Event:||JUL 05-07, 2000|
Actions (login required)