Return to search

Algebraic algorithms in combinatorial optimization.

Cheung, Ho Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 91-96). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Matroids and Matrices --- p.5 / Chapter 2.1.1 --- Examples --- p.6 / Chapter 2.1.2 --- Constructions --- p.7 / Chapter 2.1.3 --- Matroid Intersection --- p.8 / Chapter 2.1.4 --- Matroid Parity --- p.9 / Chapter 2.2 --- Matrix Formulations --- p.14 / Chapter 2.2.1 --- Graph Matching --- p.15 / Chapter 2.2.2 --- Skew-Symmetric Matrix --- p.16 / Chapter 2.2.3 --- Linear Matroid Parity --- p.21 / Chapter 2.2.4 --- Weighted Problems --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Matrix Algorithms --- p.26 / Chapter 2.3.2 --- Computing Matrix Inverse --- p.28 / Chapter 2.3.3 --- Matrix of Indeterminates --- p.32 / Chapter 2.3.4 --- Mixed Skew-symmetric Matrix --- p.34 / Chapter 2.4 --- Algebraic Algorithms for Graph Matching --- p.35 / Chapter 2.4.1 --- Matching in O{nw+1) time --- p.36 / Chapter 2.4.2 --- Matching in O(n3) time --- p.37 / Chapter 2.4.3 --- Matching in O(nw) time --- p.38 / Chapter 2.4.4 --- Weighted Algorithms --- p.39 / Chapter 2.4.5 --- Parallel Algorithms --- p.40 / Chapter 2.5 --- Algebraic Algorithms for Graph Connectivity --- p.41 / Chapter 2.5.1 --- Previous Approach --- p.41 / Chapter 2.5.2 --- Matrix Formulation Using Network Coding --- p.42 / Chapter 3 --- Linear Matroid Parity --- p.49 / Chapter 3.1 --- Introduction --- p.49 / Chapter 3.1.1 --- Problem Formulation and Previous Work --- p.50 / Chapter 3.1.2 --- Our Results --- p.52 / Chapter 3.1.3 --- Techniques --- p.55 / Chapter 3.2 --- Preliminaries --- p.56 / Chapter 3.3 --- A Simple Algebraic Algorithm for Linear Matroid Parity --- p.56 / Chapter 3.3.1 --- An 0(mr2) Algorithm --- p.56 / Chapter 3.4 --- Graph Algorithms --- p.59 / Chapter 3.4.1 --- Mader's S-Path --- p.59 / Chapter 3.4.2 --- Graphic Matroid Parity --- p.64 / Chapter 3.4.3 --- Colorful Spanning Tree --- p.66 / Chapter 3.5 --- Weighted Linear Matroid Parity --- p.69 / Chapter 3.6 --- A Faster Linear Matroid Parity Algorithm --- p.71 / Chapter 3.6.1 --- Matrix Formulation --- p.71 / Chapter 3.6.2 --- An O(mw) Algorithm --- p.74 / Chapter 3.6.3 --- An O(mrw - 1 ) Algorithm --- p.76 / Chapter 3.7 --- Maximum Cardinality Matroid Parity --- p.79 / Chapter 3.8 --- Open Problems --- p.80 / Chapter 4 --- Graph Connectivities --- p.81 / Chapter 4.1 --- Introduction --- p.81 / Chapter 4.2 --- Inverse of Well-Separable Matrix --- p.83 / Chapter 4.3 --- Directed Graphs with Good Separators --- p.86 / Chapter 4.4 --- Open Problems --- p.89

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327410
Date January 2011
ContributorsCheung, Ho Yee., 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, [4], iv, 96 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.0014 seconds