The on-line decremental connectivity in outerplanar graphs
| Autor: | Chun-Shien Lu, 呂俊賢 |
|---|---|
| Rok vydání: | 2001 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 89 A dynamic graph problem is to maintain a graph G=(V, E), where G may be updated by insertion and deletion of edges and queries concerning certain properties of G may be asked. For the dynamic connectivity problem, the queries are of the form: “Are vertices v and w connected in G ?” or “Is G connected?” A dynamic graph problem is fully dynamic if both insertions and deletions of edges are allowed. The problem is incremental if only insertions are allowed, and decremental if only deletions are allowed. Efficient dynamic graph algorithms have many applications in communication networks, computer-aided design, database systems, logic programming, incremental data flow analysis, and computational biology. In this thesis, the decremental dynamic connectivity problem in outerplanar graphs is studied. An efficient algorithm is presented. The presented algorithm requires O(n) space. After an O(n) time preprocessing, each edge deletion and connectivity query can be done in O(log n / log log n) time. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|