Return to search

Linear time algorithms for graphs close to chordal graphs.

Ho Man Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 51-54). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Statement of problems --- p.1 / Chapter 1.2 --- Notation and definitions --- p.3 / Chapter 1.3 --- Graph families --- p.4 / Chapter 1.4 --- Related work --- p.5 / Chapter 1.4.1 --- Graph modification problems --- p.5 / Chapter 1.4.2 --- Independent set --- p.6 / Chapter 1.5 --- Overview of the thesis --- p.7 / Chapter 2 --- Recognition of Nearly Chordal Graphs --- p.8 / Chapter 2.1 --- Critical edges not in triangles --- p.9 / Chapter 2.2 --- Critical edges in triangles --- p.10 / Chapter 2.3 --- A linear time algorithm --- p.13 / Chapter 3 --- Recognition of Almost Chordal Graphs --- p.15 / Chapter 3.1 --- Minimal separator --- p.16 / Chapter 3.2 --- "All chordless cycles passing through the minimal (x, z)-separator S" --- p.18 / Chapter 3.3 --- Algorithm for almost chordal graphs recognition --- p.22 / Chapter 3.4 --- Another approach to find a critical vertex if all chordless cycles pass through S --- p.26 / Chapter 3.5 --- A linear algorithm for all chordless cycles passing through S --- p.28 / Chapter 4 --- Maximum Independent Bases of Chordal Graphs --- p.32 / Chapter 4.1 --- Maximum independent base --- p.32 / Chapter 4.1.1 --- Finding a maximum independent set of a chordal graph . --- p.33 / Chapter 4.1.2 --- Another approach to prove the algorithm --- p.33 / Chapter 4.1.3 --- Maximum independent base --- p.34 / Chapter 4.1.4 --- Vertices in the maximum independent base --- p.36 / Chapter 4.1.5 --- A linear time algorithm --- p.38 / Chapter 4.2 --- Generating all maximum independent sets --- p.39 / Chapter 4.2.1 --- Relation between two maximum independent sets --- p.39 / Chapter 4.2.2 --- Algorithm --- p.40 / Chapter 4.3 --- Maximum induced split graph of a chordal graph --- p.43 / Chapter 4.3.1 --- Property of maximum induced split subgraph --- p.44 / Chapter 4.3.2 --- A linear time algorithm --- p.45 / Chapter 5 --- Concluding Remarks --- p.48 / Chapter 5.1 --- Summary of results --- p.48 / Chapter 5.2 --- Open problems --- p.48 / Bibliography --- p.51

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_324279
Date January 2003
ContributorsHo, Man Lam., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, bibliography
Formatprint, vi, 54 leaves : ill. ; 30 cm.
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0015 seconds