Return to search

Maximum K-vertex covers for some classes of graphs.

Leung Chi Wai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 52-57). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.1 / Chapter 1.2 --- Related work --- p.3 / Chapter 1.2.1 --- Fixed-parameter tractability --- p.3 / Chapter 1.2.2 --- Maximum k-vertex cover --- p.4 / Chapter 1.2.3 --- Dominating set --- p.4 / Chapter 1.3 --- Overview of the thesis --- p.5 / Chapter 2 --- Preliminaries --- p.6 / Chapter 2.1 --- Notation and definitions --- p.6 / Chapter 2.1.1 --- Basic definitions --- p.6 / Chapter 2.1.2 --- Partial t-trees --- p.7 / Chapter 2.1.3 --- Cographs --- p.9 / Chapter 2.1.4 --- Chordal graphs and interval graphs --- p.11 / Chapter 2.2 --- Upper bound --- p.12 / Chapter 2.3 --- Extension method --- p.14 / Chapter 3 --- Planar Graphs --- p.17 / Chapter 3.1 --- Trees --- p.17 / Chapter 3.2 --- Partial t-trees --- p.23 / Chapter 3.3 --- Planar graphs --- p.30 / Chapter 4 --- Perfect Graphs --- p.34 / Chapter 4.1 --- Maximum k-vertex cover in cographs --- p.34 / Chapter 4.2 --- Maximum dominating k-set in interval graphs --- p.39 / Chapter 4.3 --- Maximum k-vertex subgraph in chordal graphs --- p.46 / Chapter 4.3.1 --- Maximum k-vertex subgraph in partial t- trees --- p.46 / Chapter 4.3.2 --- Maximum k-vertex subgraph in chordal graphs --- p.47 / Chapter 5 --- Concluding Remarks --- p.49 / Chapter 5.1 --- Summary of results --- p.49 / Chapter 5.2 --- Open problems --- p.50

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_325442
Date January 2005
ContributorsLeung, Chi Wai., 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, vii, 57 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.0019 seconds