Back to search

University of Victoria (Canada)

Dynamic algorithms for chordal and interval graphs

Abstract

dc:description.abstract

We 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 × 4

Rights

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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ibarra, Louis Walter. Dynamic algorithms for chordal and interval graphs. Doctor of Philosophy Ph.D. thesis, 2018. http://hdl.handle.net/1828/9596