Please use this identifier to cite or link to this item:
Title: Representations of tolerance graphs
Authors: Eisermann, Birk
Keywords: DRNTU::Science::Physics
Issue Date: 2013
Source: Eisermann, B. (2013). Representations of tolerance graphs. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: This thesis presents research about tolerance graphs. First some of the background of the class of tolerance graphs and closely related graph classes is provided. Important properties like ’weakly chordal’ and representation models (by intervals on the real line, parallelograms in the real plane or parallelepipeds in the 3-dimensional space) are introduced. An overview of standard algorithms on tolerance graphs and related graph classes is given. We contribute an improved version of a criterion of Golumbic, Monma, Trenk about the distinction between bounded and unbounded tolerance graphs. The new criterion can recognize more tolerance graphs as bounded. Furthermore, an explicit construction of tolerance representations of bipartite tolerance graphs is presented. It can serve as a certificate of an already existing recognition algorithm of bipartite tolerance graphs. These representations as well as representations of unit tolerance graphs are shown to be of small size. In other words, there are non-negative integer tolerance representations for graphs of these two classes with a maximal integer in O(n2). For general tolerance graphs, a new bound of n22n is established, which improves the previously known bound of 1 + 5n25n. The new bound is proved to be correct by integer linear programming techniques. These techniques also yield a moderately fast recognition of tolerance graphs with a small number of vertices, although the recognition is NPcomplete.
DOI: 10.32657/10356/51122
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
TspmsG0701450H.pdf729.49 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.