Leung, Kai Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 63-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Graph Connectivity --- p.5 / Chapter 2.1.1 --- Preliminaries --- p.5 / Chapter 2.1.2 --- Edge Connectivity --- p.7 / Chapter 2.1.3 --- Vertex Connectivity --- p.7 / Chapter 2.1.4 --- Algorithms for Graph Connectivities --- p.9 / Chapter 2.1.5 --- All Pairs Edge Connectivities --- p.10 / Chapter 2.1.6 --- Edge Splitting-off --- p.11 / Chapter 2.1.7 --- Graph Separator --- p.13 / Chapter 2.1.8 --- Expander Graphs --- p.15 / Chapter 2.1.9 --- Superconcentrator --- p.17 / Chapter 2.2 --- Network Coding --- p.19 / Chapter 2.2.1 --- Concept --- p.19 / Chapter 2.2.2 --- Linear Network Coding --- p.21 / Chapter 2.2.3 --- Random Linear Network Coding --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Linear Algebraic Algorithms --- p.26 / Chapter 2.3.2 --- Nested Dissection --- p.28 / Chapter 3 --- Algorithms for Graph Connectivities --- p.35 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.1.1 --- Our Results --- p.36 / Chapter 3.1.2 --- Related Work --- p.39 / Chapter 3.1.3 --- Techniques --- p.40 / Chapter 3.1.4 --- Organization --- p.41 / Chapter 3.2 --- New Algebraic Characterization --- p.41 / Chapter 3.3 --- Connectivities in Acyclic Graph --- p.46 / Chapter 3.3.1 --- Faster Encoding Algorithms --- p.47 / Chapter 3.4 --- Directed Planar Graphs --- p.49 / Chapter 3.5 --- All Pairs Edge Connectivities --- p.53 / Chapter 3.5.1 --- Connections with Previous Work --- p.55 / Chapter 3.6 --- Edge Splitting-off --- p.56 / Chapter 3.6.1 --- Edge Splitting-off in Directed Graphs --- p.57 / Chapter 3.6.2 --- Edge Splitting-off in Undirected Graphs --- p.58 / Concluding Remarks --- p.61 / Bibliography --- p.62
Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327363 |
Date | January 2011 |
Contributors | Leung, Kai Man., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
Source Sets | The Chinese University of Hong Kong |
Language | English, Chinese |
Detected Language | English |
Type | Text, bibliography |
Format | print, [4], ii, 68 leaves : ill. ; 30 cm. |
Rights | Use 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.0017 seconds