Abstract
dc:description.abstractWe present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality, (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O( n) time, where n is the number of vertices. In the second, an insertion query runs in O(log² n) time, an insertion in O(n) time, a deletion query in O(n) time, and a deletion in O(n log n) time. We also introduce the clique-separator graph representation of a chordal graph, which provides significantly more information about the graph's structure than the well-known clique tree representation. We present fundamental properties of the clique-separator graph and additional properties when the input graph is interval. We then introduce the train tree representation of interval graphs and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n log n) time per edge insertion or deletion. The clique-separator graph may lead to dynamic algorithms for every proper subclass of chordal graphs, and the train tree may lead to fast dynamic algorithms for problems on interval graphs.
Degree
thesis:*- Level thesis:degree_level
- Doctor of Philosophy Ph.D.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ibarra, Louis Walter
- Advisor dc:contributor.supervisor
-
- King, Valerie D.
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/9596