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

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

published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (MSc)--University of Stellenbosch, 2005. / Bibliography. Also available via the Internet.

For a weighted graph with n vertices and m edges, the Minimum k-Way Cut problem is to find a partition of the vertices into k sets that minimizes the total weight of edges crossing the sets. We obtain several important structural properties of minimum multiway cuts and use them to design efficient algorithms for several multiway partition problems. We design the first algorithm for finding minimum 3-way cuts in hypergraphs, which runs in O(dmn 3) time, where d is the sum of the degrees of all the vertices. We also give an O(n 4k--lg k) algorithm for finding all minimum k-way cuts in graphs. Our algorithm is based on a divide-and-conquer method and improves all well-known existing algorithms along this divide-and-conquer method. As for approximation algorithms, we determine the tight approximation ratio of a general greedy splitting algorithm (finding a minimum k-way cut by iteratively increasing a constant number of components). Our result implies that the approximation ratio of the algorithm that iteratively increases h -- 1 components is 2 -- h/k + O(h2 /k2), which settles a well-known open problem. / For an unweighted graph and a given subset T ⊂ V of k terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of l edges (respectively, non-terminal vertices), whose removal from G separates each terminal from all the others. We show that Edge Multiterminal Cut is polynomial-time solvable for 1 = O(log n) by presenting an O(2lkT(n, m)) algorithm, where T(n, m) is the running time of finding a maximum flow in unweighted graphs. We also give three algorithms for Vertex Multiterminal Cut that run in O(k lT(n, m)), O( l!2 2l T(n, m)) and O(lk 4lT( n, m)) time respectively. Furthermore, we obtain faster algorithms for small k: Edge 3-Terminal Cut can be solved in O(1.415lT(n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059 lT(n, m)), O(2.772 lT(n, m)), O(3.349 lT(n, m)) and O(3.857 lT(n, m)) times respectively. Our results on Multiterminal Cut can be used to obtain faster algorithms for Multicut. / In this thesis, we study algorithmic issues for three closely related partition problems in graphs: k-Way Cut (k-Cut), Multiterminal Cut, and Multicut. These three problems attempt to separate a graph, by edge or vertex deletion, into several components with certain properties. The k-Way Cut (k-Cut) problem is to separate the graph into k components, the Multiterminal Cut problem is to separate a subset of vertices away from each other, and the Multicut problem is to separate some given pairs of vertices. These three problems have many applications in parallel and distributed computing, VLSI system design, clustering problems, communications network and many others. / Xiao, Mingyu. / Adviser: Andrew C. Yao. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3617. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 85-92). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

No description available.

Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (M.Sc.)--York University, 2006. Graduate Programme in Mathematics and Statistics. / Typescript. Includes bibliographical references (leaves 168-173). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR19755

Thesis (M.S.)--Auburn University, 2008. / Abstract. Vita. Includes bibliographical references (p. 19).

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2006. / Includes bibliographical references (leaves [78]-84). Also available in electronic version.