University of Waterloo
A Faster Algorithm for Recognizing Edge-Weighted Interval Graphs
Abstract
dc:description.abstractInterval graphs—the intersection graphs of one-dimensional intervals—are considered one of the most useful mathematical structures to model real life applications. Interval graphs have been widely studied since they first appeared in the literature in 1957. In 1976, Booth and Lueker introduced a data structure called PQ-trees that could recognize interval graphs in linear time; since then, several simpler linear-time algorithms have been proposed for the problem. We investigate a lesser-studied variation of interval graphs called edge-weighted interval graphs. A graph with weights on its edges is an edge-weighted interval graph if we can assign intervals to its vertices so that the weight of an edge (u, v) is equal to the length of the intersection of the intervals assigned to u and v. In 2012, Kobler, Kuhnert, and Watanabe gave an algorithm to recognize such graphs in time O(m · n), where m and n are the number of edges and vertices, respectively, of the given graph. In this thesis, we give an algorithm to recognize complete edge-weighted interval graphs in time O(m · log n). We then observe some additional properties of PQ-trees for interval graphs, and use these properties to improve the runtime of the algorithm given by Kobler et al. for recognizing general edge-weighted interval graphs to O(m · log n). As the literature for finding representations of weighted intersection graphs is scarce, we hope that the techniques presented in this thesis can be used to obtain algorithms or approximation algorithms for recognition of other kinds of weighted intersection graphs.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mahajan, Shikha
- Advisor dc:contributor.advisor
-
- Lubiw, Anna
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/11765