Show simple item record

dc.contributor.authorMahajan, Shikha 13:47:27 (GMT) 13:47:27 (GMT)
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.en
dc.publisherUniversity of Waterlooen
dc.subjectInterval Graphsen
dc.titleA Faster Algorithm for Recognizing Edge-Weighted Interval Graphsen
dc.typeMaster Thesisen
dc.pendingfalse R. Cheriton School of Computer Scienceen Scienceen of Waterlooen
uws-etd.degreeMaster of Mathematicsen
uws.contributor.advisorLubiw, Anna
uws.contributor.affiliation1Faculty of Mathematicsen

Files in this item


This item appears in the following Collection(s)

Show simple item record


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages