by Sau-ming Lau. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 131-134). / Abstract --- p.i / Acknowledgement --- p.iii / List of Tables --- p.viii / List of Figures --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Basic Concepts and Related Work --- p.9 / Chapter 2.1 --- Components of Dynamic Load Balancing Algorithms --- p.10 / Chapter 2.2 --- Classification of Load Balancing Algorithms --- p.11 / Chapter 2.2.1 --- Casavant and Kuhl's Taxonomy --- p.12 / Chapter 3 --- System Model and Assumptions --- p.19 / Chapter 3.1 --- The System Model and Assumptions --- p.19 / Chapter 3.2 --- Survey on Cost Models --- p.21 / Chapter 3.2.1 --- "Eager, Lazowska, and Zahorjan's Model" --- p.22 / Chapter 3.2.2 --- "Shivaratri, Krueger, and Singhal's Model" --- p.23 / Chapter 3.3 --- Our Cost Model --- p.24 / Chapter 3.3.1 --- Design Philosophy --- p.24 / Chapter 3.3.2 --- Polling Query Cost Model --- p.25 / Chapter 3.3.3 --- Load State Broadcasting Cost Model --- p.26 / Chapter 3.3.4 --- Task Assignment Cost Model --- p.27 / Chapter 3.3.5 --- Task Migration Cost Model --- p.28 / Chapter 3.3.6 --- Execution Priority --- p.29 / Chapter 3.3.7 --- Simulation Parameter Values --- p.31 / Chapter 3.4 --- Performance Metrics --- p.33 / Chapter 4 --- A Performance Study on Load Information Dissemination Strategies --- p.36 / Chapter 4.1 --- Algorithm Descriptions --- p.37 / Chapter 4.1.1 --- Transfer Policy --- p.37 / Chapter 4.1.2 --- Information Policy --- p.40 / Chapter 4.1.3 --- Location Policy --- p.40 / Chapter 4.1.4 --- Categorization of the Algorithms --- p.43 / Chapter 4.2 --- Simulations and Analysis of Results --- p.43 / Chapter 4.2.1 --- Performance Comparisons --- p.44 / Chapter 4.2.2 --- Effect of Imbalance Factor on AWLT Algorithms --- p.49 / Chapter 4.2.3 --- Comparison of Average Performance --- p.52 / Chapter 4.2.4 --- Raw Simulation Results --- p.54 / Chapter 4.3 --- Discussions --- p.55 / Chapter 5 --- Resolving Processor Thrashing with Batch Assignment --- p.56 / Chapter 5.1 --- The GR.batch Algorithm --- p.57 / Chapter 5.1.1 --- The Guarantee and Reservation Protocol --- p.57 / Chapter 5.1.2 --- The Location Policy --- p.58 / Chapter 5.1.3 --- Batch Size Determination --- p.60 / Chapter 5.1.4 --- The Complete GR.batch Description --- p.62 / Chapter 5.2 --- Additional Performance Metrics --- p.66 / Chapter 5.3 --- Simulations and Analysis of Results --- p.67 / Chapter 5.4 --- Discussions --- p.73 / Chapter 6 --- Applying Batch Assignment to Systems with Bursty Task Arrival Patterns --- p.75 / Chapter 6.1 --- Bursty Workload Pattern Characterization Model --- p.76 / Chapter 6.2 --- Algorithm Descriptions --- p.77 / Chapter 6.2.1 --- The GR.batch Algorithm --- p.77 / Chapter 6.2.2 --- The SK .single Algorithm --- p.77 / Chapter 6.2.3 --- Summary of Algorithm Properties --- p.77 / Chapter 6.3 --- Analysis of Simulation Results --- p.77 / Chapter 6.3.1 --- Performance Comparison --- p.79 / Chapter 6.3.2 --- Time Trace --- p.80 / Chapter 6.4 --- Discussions --- p.80 / Chapter 7 --- A Preliminary Study on Task Assignment Augmented with Migration --- p.87 / Chapter 7.1 --- Algorithm Descriptions --- p.87 / Chapter 7.1.1 --- Information Policy --- p.88 / Chapter 7.1.2 --- Location Policy --- p.88 / Chapter 7.1.3 --- Transfer Policy --- p.88 / Chapter 7.1.4 --- The Three Load Balancing Algorithms --- p.89 / Chapter 7.2 --- Simulations and Analysis of Results --- p.90 / Chapter 7.2.1 --- Even Task Service Time --- p.90 / Chapter 7.2.2 --- Uneven Task Service Time --- p.94 / Chapter 7.3 --- Discussions --- p.99 / Chapter 8 --- Assignment Augmented with Migration Revisited --- p.100 / Chapter 8.1 --- Algorithm Descriptions --- p.100 / Chapter 8.1.1 --- The GR.BATCH.A Algorithm --- p.101 / Chapter 8.1.2 --- The SK.SINGLE.AM Algorithm --- p.101 / Chapter 8.1.3 --- Summary of Algorithm Properties --- p.101 / Chapter 8.2 --- Simulations and Analysis of Results --- p.101 / Chapter 8.2.1 --- Performance Comparisons --- p.102 / Chapter 8.2.2 --- Effect of Workload Imbalance --- p.105 / Chapter 8.3 --- Discussions --- p.106 / Chapter 9 --- Applying Batch Transfer to Heterogeneous Systems with Many Task Classes --- p.108 / Chapter 9.1 --- Heterogeneous System Model --- p.109 / Chapter 9.1.1 --- Processing Node Specification --- p.110 / Chapter 9.1.2 --- Task Type Specification --- p.111 / Chapter 9.1.3 --- Workload State Measurement --- p.112 / Chapter 9.1.4 --- Task Selection Candidates --- p.113 / Chapter 9.2 --- Algorithm Descriptions --- p.115 / Chapter 9.2.1 --- First Category ´ؤ The Sk .single Variations --- p.115 / Chapter 9.2.2 --- Second Category ´ؤ The GR. batch Variation Modeled with SSP --- p.117 / Chapter 9.3 --- Analysis of Simulation Results --- p.123 / Chapter 10 --- Conclusions and Future Work --- p.127 / Bibliography --- p.131 / Appendix A System Model Notations and Definitions --- p.131 / Appendix A.1 Processing Node Model --- p.131 / Appendix A.2 Cost Models --- p.132 / Appendix A.3 Load Measurement --- p.134 / Appendix A.4 Batch Size Determination Rules --- p.135 / Appendix A.5 Bursty Arrivals Modeling --- p.135 / Appendix A.6 Heterogeneous Systems Modeling --- p.135 / Appendix B Shivaratri and Krueger's Location Policy --- p.137

by Lau Shek Kwan Mark. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 85-86). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Historical Background --- p.2 / Chapter 1.2 --- Introduction to Autostereograms --- p.5 / Chapter 1.2.1 --- Geometrical Model --- p.5 / Chapter 1.2.2 --- IS-separation --- p.6 / Chapter 1.2.3 --- The Hidden Surfaces --- p.7 / Chapter 1.2.4 --- False Target and Echo --- p.8 / Chapter 1.3 --- The Autostereogram Generation Algorithm --- p.10 / Chapter 1.4 --- Further Applications of Autostereograms --- p.15 / Chapter 1.5 --- Organization of Thesis --- p.17 / Chapter 2 --- Analysis of Autostereograms --- p.20 / Chapter 2.1 --- IS-separation --- p.21 / Chapter 2.2 --- Autostereogram Generations --- p.25 / Chapter 2.3 --- Surface Reconstructions --- p.26 / Chapter 2.4 --- Visual Distortions --- p.28 / Chapter 2.4.1 --- Problem Model For Vertical Distortions --- p.30 / Chapter 2.4.2 --- Change of Depth Field --- p.33 / Chapter 2.4.3 --- Non-linear Distortion --- p.35 / Chapter 2.4.4 --- Lateral Distortions --- p.38 / Chapter 2.5 --- Discrete Autostereograms --- p.40 / Chapter 2.5.1 --- Truncation Problem --- p.41 / Chapter 2.5.2 --- Computer Algorithms for Autostereograms --- p.42 / Chapter 3 --- Analysis of Echoes --- p.48 / Chapter 3.1 --- Causes of Echoes --- p.49 / Chapter 3.1.1 --- Insufficient Lengths of The Periods of Repeating Patterns --- p.51 / Chapter 3.1.2 --- Overlapping of Copying Steps --- p.51 / Chapter 3.2 --- Avoidance of Type 1 Echoes --- p.52 / Chapter 3.3 --- Avoidance of Type 2 Echoes --- p.55 / Chapter 3.4 --- Autostereogram Encoding Any Surface --- p.58 / Chapter 4 --- Autostereogram as A Cryptosystem --- p.65 / Chapter 4.1 --- Introduction to Cryptography --- p.66 / Chapter 4.1.1 --- Mathematical Structure of Cryptosystems --- p.67 / Chapter 4.1.2 --- A Classical Cryptosystem´ؤSubstitution Cipher --- p.68 / Chapter 4.2 --- Autostereogram as a Cryptosystem --- p.72 / Chapter 4.2.1 --- Autostereogram as a Variation of Substitution Cipher --- p.74 / Chapter 4.2.2 --- Practical Considerations --- p.76 / Chapter 5 --- Conclusion and Future Works --- p.79 / Chapter 5.1 --- Future Works --- p.80 / Chapter A --- Excessive Removal of Copying Steps --- p.81 / Chapter B --- Publications Resulted from the Study --- p.84

Lee, Pak-Ching. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 80-83). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Work --- p.5 / Chapter 3 --- Tree-Based Group Diffie-Hellman --- p.9 / Chapter 4 --- Interval-Based Distributed Rekeying Algorithms --- p.14 / Chapter 4.1 --- Rebuild Algorithm --- p.15 / Chapter 4.2 --- Batch Algorithm --- p.16 / Chapter 4.3 --- Queue-batch Algorithm --- p.19 / Chapter 5 --- Performance Evaluation --- p.22 / Chapter 5.1 --- Mathematical Analysis --- p.22 / Chapter 5.1.1 --- Analysis of the Rebuild Algorithm --- p.24 / Chapter 5.1.2 --- Analysis of the Batch Algorithm --- p.25 / Chapter 5.1.3 --- Analysis of the Queue-batch Algorithm --- p.30 / Chapter 5.2 --- Experiments --- p.31 / Chapter 5.3 --- Discussion of the experimental results --- p.35 / Chapter 6 --- Authenticated Tree-Based Group Diffie-Hellman --- p.43 / Chapter 6.1 --- Description of A-TGDH --- p.44 / Chapter 6.2 --- Security Analysis --- p.47 / Chapter 7 --- Implementation and Applications --- p.50 / Chapter 7.1 --- Leader and Sponsors --- p.51 / Chapter 7.1.1 --- Leader --- p.51 / Chapter 7.1.2 --- Sponsors --- p.53 / Chapter 7.1.3 --- Rekeying Operation --- p.56 / Chapter 7.2 --- System Architecture --- p.57 / Chapter 7.2.1 --- System Preliminaries --- p.57 / Chapter 7.2.2 --- System Components --- p.58 / Chapter 7.2.3 --- Implementation Considerations --- p.64 / Chapter 7.3 --- SGCL API --- p.65 / Chapter 7.4 --- Experiments --- p.67 / Chapter 7.5 --- Applications --- p.72 / Chapter 7.6 --- Future Extensions --- p.75 / Chapter 8 --- Conclusions and Future Directions --- p.76 / Chapter 8.1 --- Conclusions --- p.76 / Chapter 8.2 --- Future Directions --- p.77 / Chapter 8.2.1 --- Construction of a Hybrid Key Tree with the Physical and Logical Properties --- p.77 / Chapter 8.2.2 --- Extended Implementation --- p.79 / Bibliography --- p.80

There is a long history of research in theoretical computer science devoted to designing efficient algorithms for graph problems. In many modern applications the graph in question is changing over time, and we would like to avoid rerunning our algorithm on the entire graph every time a small change occurs. The evolving nature of graphs motivates the dynamic graph model, in which the goal is to minimize the amount of work needed to reoptimize the solution when the graph changes. There is a large body of literature on dynamic algorithms for basic problems that arise in graphs. This thesis presents several improved dynamic algorithms for two fundamental graph problems: shortest paths, and matching.

by Mei Long. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 93-98). / Abstracts in English and Chinese. / Table of Contents --- p.v / Abstract --- p.viii / Acknowledgements --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Satisfiability Problem --- p.4 / Chapter 2.1 --- Satisfiability Problem --- p.5 / Chapter 2.1.1 --- Basic Definition --- p.5 / Chapter 2.1.2 --- Phase Transitions --- p.5 / Chapter 2.2 --- History --- p.6 / Chapter 2.3 --- The Basic Search Algorithm --- p.8 / Chapter 2.4 --- Some Improvements to the Basic Algorithm --- p.9 / Chapter 2.4.1 --- Satz by Chu-Min Li --- p.9 / Chapter 2.4.2 --- Heuristics and Local Search --- p.12 / Chapter 2.4.3 --- Relaxation --- p.13 / Chapter 2.5 --- Benchmarks --- p.14 / Chapter 2.5.1 --- Specific Problems --- p.14 / Chapter 2.5.2 --- Randomly Generated Problems --- p.14 / Chapter 2.6 --- Software and Internet Information for SAT solving --- p.16 / Chapter 2.6.1 --- Stochastic Local Search Algorithms (incomplete) --- p.16 / Chapter 2.6.2 --- Systematic Search Algorithms (complete) --- p.16 / Chapter 2.6.3 --- Some useful Links to SAT Related Sites --- p.17 / Chapter 3 --- Integer Programming Formulation for Logic Problem --- p.18 / Chapter 3.1 --- SAT Problem --- p.19 / Chapter 3.2 --- MAXSAT Problem --- p.19 / Chapter 3.3 --- Logical Inference Problem --- p.19 / Chapter 3.4 --- Weighted Exact Satisfiability Problem --- p.20 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.22 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.22 / Chapter 4.2 --- Integer Programming Model for 3-SAT --- p.23 / Chapter 4.3 --- The Equivalence of the SAT and the IP --- p.23 / Chapter 4.4 --- Example --- p.24 / Chapter 5 --- Integer Solvability of Linear Programs --- p.27 / Chapter 5.1 --- Unimodularity --- p.27 / Chapter 5.2 --- Totally Unimodularity --- p.28 / Chapter 5.3 --- Some Results on Recognition of Linear Solvability of IP --- p.32 / Chapter 6 --- TU Based Matrix Research Results --- p.33 / Chapter 6.1 --- 2x2 Matrix's TU Property --- p.33 / Chapter 6.2 --- Extended Integer Programming Model for SAT --- p.34 / Chapter 6.3 --- 3x3 Matrix's TU Property --- p.35 / Chapter 7 --- Totally Unimodularity Based Branching-and-Bound Algorithm --- p.38 / Chapter 7.1 --- Introduction --- p.38 / Chapter 7.1.1 --- Enumeration Trees --- p.39 / Chapter 7.1.2 --- The Concept of Branch and Bound --- p.42 / Chapter 7.2 --- TU Based Branching Rule --- p.43 / Chapter 7.2.1 --- How to sort variables based on 2x2 submatrices --- p.43 / Chapter 7.2.2 --- How to sort the rest variables --- p.45 / Chapter 7.3 --- TU Based Bounding Rule --- p.46 / Chapter 7.4 --- TU Based Branch-and-Bound Algorithm --- p.47 / Chapter 7.5 --- Example --- p.49 / Chapter 8 --- Numerical Result --- p.57 / Chapter 8.1 --- Experimental Result --- p.57 / Chapter 8.2 --- Statistical Results of ILOG CPLEX --- p.59 / Chapter 9 --- Conclusions --- p.61 / Chapter 9.1 --- Contributions --- p.61 / Chapter 9.2 --- Future Work --- p.62 / Chapter A --- The Coefficient Matrix A for Example in Chapter 7 --- p.64 / Chapter B --- The Detailed Numerical Information of Solution Process for Exam- ple in Chapter 7 --- p.66 / Chapter C --- Experimental Result --- p.67 / Chapter C.1 --- "# of variables: 20, # of clauses: 91" --- p.67 / Chapter C.2 --- "# of variables: 50, # of clauses: 218" --- p.70 / Chapter C.3 --- # of variables: 75，# of clauses: 325 --- p.73 / Chapter C.4 --- "# of variables: 100, # of clauses: 430" --- p.76 / Chapter D --- Experimental Result of ILOG CPLEX --- p.80 / Chapter D.1 --- # of variables: 20´ة # of clauses: 91 --- p.80 / Chapter D.2 --- # of variables: 50，#of clauses: 218 --- p.83 / Chapter D.3 --- # of variables: 75，# of clauses: 325 --- p.86 / Chapter D.4 --- "# of variables: 100, # of clauses: 430" --- p.89 / Bibliography --- p.93

Lee Lok Hang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 87-93). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Sensors and Sensor Networks --- p.3 / Chapter 1.2 --- Sensor Network Deployment --- p.7 / Chapter 1.3 --- Motivations --- p.7 / Chapter 1.4 --- Contributions --- p.9 / Chapter 1.5 --- Thesis Organization --- p.10 / Chapter 2 --- Literature Review --- p.11 / Chapter 2.1 --- Data Cube --- p.11 / Chapter 2.2 --- Data Aggregation in Sensor Networks --- p.12 / Chapter 2.2.1 --- Hierarchical Data Aggregation --- p.13 / Chapter 2.2.2 --- Gossip-based Aggregation --- p.13 / Chapter 2.2.3 --- Hierarchical Gossip Aggregation --- p.13 / Chapter 2.3 --- GAF Algorithm --- p.14 / Chapter 2.4 --- Concurrency Control --- p.17 / Chapter 2.4.1 --- Two-phase Locking --- p.17 / Chapter 2.4.2 --- Timestamp Ordering --- p.18 / Chapter 3 --- Building Distributed Data Cubes in Sensor Network --- p.20 / Chapter 3.1 --- Aggregation Operators --- p.21 / Chapter 3.2 --- Distributed Prefix (PS) Sum Data Cube --- p.22 / Chapter 3.2.1 --- Prefix Sum (PS) Data Cube --- p.22 / Chapter 3.2.2 --- Notations --- p.24 / Chapter 3.2.3 --- Querying a PS Data Cube --- p.25 / Chapter 3.2.4 --- Building Distributed PS Data Cube --- p.27 / Chapter 3.2.5 --- Time Bounds --- p.32 / Chapter 3.2.6 --- Fast Aggregate Queries on Multiple Regions --- p.37 / Chapter 3.2.7 --- Simulation Results --- p.43 / Chapter 3.3 --- Distributed Local Prefix Sum (LPS) Data Cube --- p.50 / Chapter 3.3.1 --- Local Prefix Sum Data Cube --- p.52 / Chapter 3.3.2 --- Notations --- p.55 / Chapter 3.3.3 --- Querying an LPS Data Cube --- p.56 / Chapter 3.3.4 --- Building Distributed LPS Data Cube --- p.61 / Chapter 3.3.5 --- Time Bounds --- p.63 / Chapter 3.3.6 --- Fast Aggregate Queries on Multiple Regions --- p.67 / Chapter 3.3.7 --- Simulation Results --- p.68 / Chapter 3.3.8 --- Distributed PS Data Cube Vs Distributed LPS Data Cube --- p.74 / Chapter 4 --- Concurrency Control and Consistency in Sensor Networks --- p.76 / Chapter 4.1 --- Data Inconsistency in Sensor Networks --- p.76 / Chapter 4.2 --- Traditional Concurrency Control Protocols and Sensor Networks --- p.80 / Chapter 4.3 --- The Consistent Retrieval of Data from Distributed Data Cubes --- p.81 / Chapter 5 --- Conclusions --- p.85 / References --- p.87 / Appendix --- p.94 / A Publications --- p.94

by Sze-Kin Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 71-76). / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Work --- p.6 / Chapter 2.1 --- Sequence query processing --- p.8 / Chapter 2.2 --- Text sequence searching --- p.8 / Chapter 2.3 --- Numerical sequence searching --- p.11 / Chapter 2.4 --- Indexing schemes --- p.17 / Chapter 3 --- Sequence Data Searching using the Projection Algorithm --- p.21 / Chapter 3.1 --- Sequence Similarity --- p.21 / Chapter 3.2 --- Searching Method --- p.24 / Chapter 3.2.1 --- Sequential Algorithm --- p.24 / Chapter 3.2.2 --- Projection Algorithm --- p.25 / Chapter 3.3 --- Handling Scaling Problem by the Projection Algorithm --- p.33 / Chapter 4 --- Sequence Data Searching using Hashing Algorithm --- p.37 / Chapter 4.1 --- Sequence Similarity --- p.37 / Chapter 4.2 --- Hashing algorithm --- p.39 / Chapter 4.2.1 --- Motivation of the Algorithm --- p.40 / Chapter 4.2.2 --- Hashing Algorithm using dynamic hash function --- p.44 / Chapter 4.2.3 --- Handling Scaling Problem by the Hashing Algorithm --- p.47 / Chapter 5 --- Comparisons between algorithms --- p.50 / Chapter 5.1 --- Performance comparison with the sequence searching algorithms --- p.54 / Chapter 5.2 --- Comparison between indexing structures --- p.54 / Chapter 5.3 --- Comparison between sequence searching algorithms in coping some deficits --- p.55 / Chapter 6 --- Performance Evaluation --- p.58 / Chapter 6.1 --- Performance Evaluation using Projection Algorithm --- p.58 / Chapter 6.2 --- Performance Evaluation using Hashing Algorithm --- p.61 / Chapter 7 --- Conclusion --- p.66 / Chapter 7.1 --- Motivation of the thesis --- p.66 / Chapter 7.1.1 --- Insufficiency of Euclidean distance --- p.67 / Chapter 7.1.2 --- Insufficiency of orthonormal transforms --- p.67 / Chapter 7.1.3 --- Insufficiency of multi-dimensional indexing structure --- p.68 / Chapter 7.2 --- Major contribution --- p.68 / Chapter 7.2.1 --- Projection algorithm --- p.68 / Chapter 7.2.2 --- Hashing algorithm --- p.69 / Chapter 7.3 --- Future work --- p.70 / Bibliography --- p.71

Yung, Chun Kong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 121-129). / Abstracts in English and Chinese. / Chapter 1 --- Overview --- p.2 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Graphs and Edge-connectivitv --- p.7 / Chapter 2.1.1 --- Subgraphs --- p.9 / Chapter 2.1.2 --- Cut and Edge-Connectivitv --- p.10 / Chapter 2.1.3 --- Menger's Theorem --- p.12 / Chapter 2.2 --- Edge Splitting-off --- p.13 / Chapter 2.2.1 --- The Basics --- p.15 / Chapter 2.2.1.1 --- Supermodular and Submodular Set Functions --- p.16 / Chapter 2.2.1.2 --- Set Functions regarding Edge-Connectivity --- p.17 / Chapter 2.2.1.3 --- Dangerous and Tight Sets --- p.18 / Chapter 2.2.2 --- Proof of Mader's Theorem --- p.20 / Chapter 2.2.3 --- Global Arc-Connectivity Setting --- p.23 / Chapter 2.2.3.1 --- Local Arc-Connectivity Setting --- p.25 / Chapter 2.2.4 --- Incorporating Additional Properties --- p.26 / Chapter 2.2.4.1 --- Non-Admissibility Graph Method --- p.27 / Chapter 2.3 --- Edge-Connectivity Problems --- p.29 / Chapter 2.3.1 --- Degree Bounded Network Design Problems --- p.30 / Chapter 2.3.1.1 --- Metric Cost Assumption --- p.31 / Chapter 2.3.2 --- Edge-Connectivitv Augmentation Problems --- p.33 / Chapter 2.3.2.1 --- Prank's Framework --- p.34 / Chapter 2.3.2.2 --- Constrained Edge-Connectivity Augmentation Problems --- p.36 / Chapter 2.3.3 --- Edge Splitting-off Problems --- p.39 / Chapter 2.4 --- Edge Splitting-off Algorithms --- p.40 / Chapter 2.4.1 --- Fastest Algorithms --- p.41 / Chapter 2.4.2 --- An Intuitive Approach --- p.42 / Chapter 2.4.3 --- Global Connectivity Settings --- p.42 / Chapter 2.4.3.1 --- Legal Ordering --- p.43 / Chapter 2.4.3.2 --- Edmonds' Arborescences --- p.44 / Chapter 2.4.4 --- Local Edge-Connectivity Setting --- p.45 / Chapter 3 --- Degree Bounded Network Design Problem with Metric Cost --- p.47 / Chapter 3.1 --- Christofides'-like Algorithm --- p.49 / Chapter 3.2 --- Simplicity-Preserving Edge Splitting-Off --- p.50 / Chapter 3.2.1 --- Proof of Theorem 3.3 --- p.51 / Chapter 3.3 --- Approximation Algorithms for Network Design Problems --- p.56 / Chapter 3.3.1 --- Removing Redundant Edges --- p.57 / Chapter 3.3.2 --- Perfect Matching --- p.58 / Chapter 3.3.3 --- Edge Splitting-Off Restoring Simplicity --- p.59 / Chapter 3.4 --- Results in Different Settings --- p.60 / Chapter 3.4.1 --- Global Edge-Connectivity --- p.61 / Chapter 3.4.2 --- Local Edge-Connectivity --- p.62 / Chapter 4 --- Constrained Edge Splitting-off --- p.64 / Chapter 4.1 --- Preliminaries --- p.66 / Chapter 4.2 --- General Constrained Edge Splitting-off Lemma --- p.68 / Chapter 4.3 --- Structural Properties of Non-Admissible Pairs --- p.69 / Chapter 4.3.1 --- Some Useful Lemmas --- p.70 / Chapter 4.3.2 --- An Upper Bound on \Dp\ --- p.71 / Chapter 4.3.3 --- An Inductive Argument --- p.73 / Chapter 4.4 --- Non-Admissibility Graph and Constraint Graph --- p.75 / Chapter 4.4.1 --- Vertex Set Partition Constraint --- p.76 / Chapter 4.4.2 --- Graph Simplicity Constraint --- p.77 / Chapter 4.4.3 --- Simultaneous Graph Constraint --- p.78 / Chapter 4.4.4 --- Tight Sufficient Conditions --- p.79 / Chapter 4.5 --- Global Arc-Connectivity Setting --- p.79 / Chapter 4.5.1 --- Proof of Lemma 4.15 --- p.81 / Chapter 5 --- Constrained Edge-Connectivity Augmentation Problem --- p.83 / Chapter 5.1 --- Preliminaries --- p.84 / Chapter 5.2 --- Additive Approximation Algorithms --- p.87 / Chapter 5.2.1 --- Edge-Connectivitv Augmentation Preserving Vertex Set Partition --- p.87 / Chapter 5.2.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.91 / Chapter 5.2.3 --- Simultaneous-Graph Edge-Connectivity Augmentation --- p.93 / Chapter 5.3 --- Global Arc-Connectivity Setting --- p.95 / Chapter 5.3.1 --- Edge-Connectivity Augmentation Preserving Vertex Set Partition --- p.95 / Chapter 5.3.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.97 / Chapter 5.3.3 --- Simultaneous Edge-Connectivity Augmentation --- p.98 / Chapter 6 --- Efficient Edge Splitting-off Algorithm --- p.100 / Chapter 6.l --- Preliminaries --- p.102 / Chapter 6.1.1 --- Efficient Tools for Edge-Connectivity Problems --- p.103 / Chapter 6.1.2 --- An Alternative Proof of Mader's Theorem --- p.104 / Chapter 6.2 --- Framework for Complete Edge Splitting-off --- p.105 / Chapter 6.2.1 --- Proof of Lemma 6.5 --- p.106 / Chapter 6.3 --- Efficient Splitting-off Attempt --- p.108 / Chapter 6.3.1 --- Indicator Vertex --- p.109 / Chapter 6.3.2 --- Splitting-off to Capacity --- p.112 / Chapter 6.4 --- Randomized and Parallelized Edge Splitting-off Algorithm --- p.113 / Chapter 6.5 --- Deterministic Edge Splitting-off Algorithm --- p.114 / Chapter 6.6 --- Algorithms in Other Settings --- p.115 / Chapter 6.6.1 --- Edge Splitting-off in Network Design Problems --- p.115 / Chapter 6.6.2 --- Constrained Edge Splitting-off --- p.116 / Chapter 7 --- Concluding Remarks --- p.119 / Bibliography --- p.121

As the Application-Specific Integrated Circuit(ASIC) technology develops to the trend of high density and modulization, the ASIC device market has been dominated gradually by the more complex Erasable Programmable Logic Devices (EPLDs) and the Field Programmable Gate Array(FPGAs) instead of the ordinally Programmable Logic Devices(PLDs). Meanwhile, the design automation system for such programmable devices has also moved from schematic entry design to high level hardware description language entry design. Usually, the whole design automation process consists of three phrases, the high level hardware description language compiler, the logic synthesis stage and the layout synthesis stage. Though the layout synthesis stage contains placement and routing, for some highly restricted connection architecture devices, placement and routing have to be considered together as a fitting problem. This thesis concentrated on the utilization of the Heuristic methods, which can be described as vertex ordering and global vertices number estimation, on an Architecture-Driven Partitioning fitting algorithm. The test results showed that the heuristic algorithm can beat the comparable algorithm in several fields. These prove the correctness of our heuristic methods and they can be used to guide the future work on the fitting problem of other similar programmable devices.

In this thesis an attempt has been made to develop a fast algorithm to compress images. The Reed-Muller compression algorithm which was introduced by Reddy & Pai [3] is fast, but the compression factor is too low when compared to the other methods. In this thesis first research has been done to improve this method by generalizing the Reed-Muller transform to the fixed polarity Reed-Muller form. This thesis shows that the Fixed Polarity Reed-Muller transform does not improve the compression factor enough to warrant its use as an image compression method. The paper, by Reddy & Pai [3], on Reed-Muller image compression has been criticized, and it was shown that some crucial errors in this paper make it impossible to evaluate the quality and compression factors of their approach. Finally a simple and fast method for image compression has been introduced. This method has taken advantage of the high correlation between the adjacent pixels of an image. If the matrix of pixel values of an image is divided into bit planes from the Most Significant Bit (MSB) plane to the Least Significant Bit (LSB) plane, most of the adjacent bits in the MSB planes (MSB, 2nd MSB, 3rd MSB and 4th MSB) are the same. Using this fact a method has been developed by Xoring the adjacent lines of the MSBs planes bit by bit, and Xoring the resulting planes bit by bit. It has been shown that this method gives a much better compression factor, and can be realized by much simpler hardware compared to Reed-Muller image compression method.