Rectilinear Steiner minimum tree (RSMT) problem asks for a shortest tree spanning a set of given terminals using only horizontal and vertical lines. Construction of RSMTs is an important problem in VLSI physical design. It is useful for both the detailed and global routing steps, and it is important for congestion, wire length and timing estimations during the floorplanning or placement step. The original RSMT problem assumes no obstacle in the routing region. However, in today’s designs, there can be many routing blockages, like macro cells, IP blocks and pre-routed nets. Therefore, the RSMT problem with blockages has become an important problem in practice and has received a lot of research attentions in the recent years. The RSMT problem has been shown to be NP-complete, and the introduction of obstacles has made this problem even more complicated. / In the first part of this thesis, we propose an exact algorithm, called ObSteiner, for the construction of obstacle-avoiding RSMT (OARSMT) in the presence of complex rectilinear obstacles. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a RSMT. We modify and extend the algorithm to allow rectilinear obstacles in the routing region. We prove that by adding virtual terminals to each routing obstacle, the FSTs in the presence of obstacles will follow some very simple structures. A two-phase approach is then developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Experimental results show that ObSteiner is able to handle problems with hundreds of terminals in the presence of up to two thousand obstacles, generating an optimal solution in a reasonable amount of time. / In the second part of this thesis, we propose the OARSMT problem with slew constraints over obstacles. In modern VLSI designs, obstacles usually block a fraction of metal layers only making it possible to route over the obstacles. However, since buffers cannot be place on top of any obstacle, we should avoid routing long wires over obstacles. Therefore, we impose the slew constraints for the interconnects that are routed over obstacles. To deal with this problem, we analyze the optimal solutions and prove that the internal trees with signal direction over an obstacle will follow some simple structures. Based on this observation, we propose an exact algorithm, called ObSteiner with slew constraints, that is able to find an optimal solution in the extended Hanan grid. Experimental results show that the proposed algorithm is able to reduce nearly 5% routing resources on average in comparison with the OARSMT algorithm and is also very much faster. / Huang, Tao. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves [137]-144). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- The rectilinear Steiner minimum tree problem --- p.1 / Chapter 1.2 --- Applications --- p.3 / Chapter 1.3 --- Obstacle consideration --- p.5 / Chapter 1.4 --- Thesis outline --- p.6 / Chapter 1.5 --- Thesis contributions --- p.8 / Chapter 2 --- Background --- p.11 / Chapter 2.1 --- RSMT algorithms --- p.11 / Chapter 2.1.1 --- Heuristics --- p.11 / Chapter 2.1.2 --- Exact algorithms --- p.20 / Chapter 2.2 --- OARSMT algorithms --- p.30 / Chapter 2.2.1 --- Heuristics --- p.30 / Chapter 2.2.2 --- Exact algorithms --- p.33 / Chapter 3 --- ObSteiner - an exact OARSMT algorithm --- p.37 / Chapter 3.1 --- Introduction --- p.38 / Chapter 3.2 --- Preliminaries --- p.39 / Chapter 3.2.1 --- OARSMT problem formulation --- p.39 / Chapter 3.2.2 --- An exact RSMT algorithm --- p.40 / Chapter 3.3 --- OARSMT decomposition --- p.42 / Chapter 3.3.1 --- Full Steiner trees among complex obstacles --- p.42 / Chapter 3.3.2 --- More Theoretical results --- p.59 / Chapter 3.4 --- OARSMT construction --- p.62 / Chapter 3.4.1 --- FST generation --- p.62 / Chapter 3.4.2 --- Pruning of FSTs --- p.66 / Chapter 3.4.3 --- FST concatenation --- p.71 / Chapter 3.5 --- Incremental construction --- p.82 / Chapter 3.6 --- Experiments --- p.83 / Chapter 4 --- ObSteiner with slew constraints --- p.97 / Chapter 4.1 --- Introduction --- p.97 / Chapter 4.2 --- Problem Formulation --- p.100 / Chapter 4.3 --- Overview of our approach --- p.103 / Chapter 4.4 --- Internal tree structures in an optimal solution --- p.103 / Chapter 4.5 --- Algorithm --- p.126 / Chapter 4.5.1 --- EFST and SCIFST generation --- p.127 / Chapter 4.5.2 --- Concatenation --- p.129 / Chapter 4.5.3 --- Incremental construction --- p.131 / Chapter 4.6 --- Experiments --- p.131 / Chapter 5 --- Conclusion --- p.135 / Bibliography --- p.137

by Cheung King Lum Kingly. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 108-110). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Problems in Content-Based Indexing --- p.2 / Chapter 1.3 --- Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.4 / Chapter 2 --- Content-Based Indexing Structures --- p.5 / Chapter 2.1 --- R-Tree --- p.6 / Chapter 2.2 --- R+-Tree --- p.8 / Chapter 2.3 --- R*-Tree --- p.11 / Chapter 3 --- Searching in Both R-Tree and R*-Tree --- p.15 / Chapter 3.1 --- Exact Search --- p.15 / Chapter 3.2 --- Nearest Neighbor Search --- p.19 / Chapter 3.2.1 --- Definition of Searching Metrics --- p.19 / Chapter 3.2.2 --- Pruning Heuristics --- p.21 / Chapter 3.2.3 --- Nearest Neighbor Search Algorithm --- p.24 / Chapter 3.2.4 --- Generalization to N-Nearest Neighbor Search --- p.25 / Chapter 4 --- An Improved Nearest Neighbor Search Algorithm for R-Tree --- p.29 / Chapter 4.1 --- Introduction --- p.29 / Chapter 4.2 --- New Pruning Heuristics --- p.31 / Chapter 4.3 --- An Improved Nearest Neighbor Search Algorithm --- p.34 / Chapter 4.4 --- Replacing Heuristics --- p.36 / Chapter 4.5 --- N-Nearest Neighbor Search --- p.41 / Chapter 4.6 --- Performance Evaluation --- p.45 / Chapter 5 --- Overlapping Nodes in R-Tree and R*-Tree --- p.53 / Chapter 5.1 --- Overlapping Nodes --- p.54 / Chapter 5.2 --- Problem Induced By Overlapping Nodes --- p.57 / Chapter 5.2.1 --- Backtracking --- p.57 / Chapter 5.2.2 --- Inefficient Exact Search --- p.57 / Chapter 5.2.3 --- Inefficient Nearest Neighbor Search --- p.60 / Chapter 6 --- Redundancy On R-Tree --- p.64 / Chapter 6.1 --- Motivation --- p.64 / Chapter 6.2 --- Adding Redundancy on Index Tree --- p.65 / Chapter 6.3 --- R-Tree with Redundancy --- p.66 / Chapter 6.3.1 --- Previous Models of R-Tree with Redundancy --- p.66 / Chapter 6.3.2 --- Redundant R-Tree --- p.70 / Chapter 6.3.3 --- Level List --- p.71 / Chapter 6.3.4 --- Inserting Redundancy to R-Tree --- p.72 / Chapter 6.3.5 --- Properties of Redundant R-Tree --- p.77 / Chapter 7 --- Searching in Redundant R-Tree --- p.82 / Chapter 7.1 --- Exact Search --- p.82 / Chapter 7.2 --- Nearest Neighbor Search --- p.86 / Chapter 7.3 --- Avoidance of Multiple Accesses --- p.89 / Chapter 8 --- Experiment --- p.90 / Chapter 8.1 --- Experimental Setup --- p.90 / Chapter 8.2 --- Exact Search --- p.91 / Chapter 8.2.1 --- Clustered Data --- p.91 / Chapter 8.2.2 --- Real Data --- p.93 / Chapter 8.3 --- Nearest Neighbor Search --- p.95 / Chapter 8.3.1 --- Clustered Data --- p.95 / Chapter 8.3.2 --- Uniform Data --- p.98 / Chapter 8.3.3 --- Real Data --- p.100 / Chapter 8.4 --- Discussion --- p.102 / Chapter 9 --- Conclusions and Future Research --- p.105 / Chapter 9.1 --- Conclusions --- p.105 / Chapter 9.2 --- Future Research --- p.106 / Bibliography --- p.108

Orientador: Thiago de Melo / Banca: Elíris Cristina Rizziolli / Banca: Luiz Roberto Hartmann Junior / Resumo: Neste trabalho estudamos a Teoria de Grafos e a aplicamos na solução de alguns problemas clássicos, como por exemplo O Problema das Pontes de Königsberg, O Problema do Caixeiro Viajante, Classificação dos Poliedros Regulares e Coloração de Mapas. As ferramentas básicas foram Topologia Geral e Álgebra / Abstract: In this work we study Graph Theory and we apply it in the solution of some classical problems, for example Königsberg Bridges Problem, Travelling Salesman Problem, Classification of Regular Polyhedra and Map Coloring. The prerequisites are General Topology and Algebra / Mestre

Graph theory and its use in school mathematics This thesis deals with the inclusion of some problems of graph theory in education at secondary school. It contains the necessary theory for teachers as well as several examples of graph theory in school mathematics in elementary school; moreover it describes several well-known problems, which can be solved using graph theory. The work also includes preparation of two lessons. The theme of the first one is drawing in one stroke and an Eulerian cycle in general. Second topic is dedicated to mazes and labyrinths, their transformation to graph and few algorithms for passing through the maze. In the experimental part, the author examines whether the students are able to understand the selected parts of graph theory, and whether they find this topic more interesting than the usual mathematics they are used to at school. The results of this experiment are then compared for children from two types of lower secondary schools.

As dificuldades no aprendizado da leitura podem ter uma causa neurológica ocasionada por fatores genéticos ou ambientais. O presente trabalho integra modelos matemáticos e neurocientíficos acerca dos processos neurais responsáveis pela leitura para estudar a dinâmica cerebral de alunos com e sem dificuldades no aprendizado da leitura. Utiliza-se, nesse estudo, uma técnica de mapeamento cerebral que considera o cérebro como uma rede complexa, onde os neurônios de diversas áreas cerebrais podem se organizar em subredes permitindo a execução paralela de diversos processos neurais. Mostra-se que os agrupamentos das áreas cerebrais de ambos os grupos, obtidos através de análise fatorial, são condizentes com modelos correntes em neurociências que sugerem para a leitura duas possíveis vias neurais, além do envolvimento de componentes de controle atencional (funções executivas). / Reading learning difficulties can be caused by genetic or environmental factors. The present work integrate graph theory and models from neuroscience about the neurological processes involved in reading to study the cerebral dynamics of children with and without learning difficulties. The brain mapping technique used in the present study, considers the brain as a complex network where neurons from several areas can be organized on sub-networks allowing a parallel execution of several neural processes. It is shown that the brain areas associations disclosed by factorial analysis, are congruent with the neuroscientific models that consider the existence of two possible neurological routes involved in reading besides the participation of the executive functions.

A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. / The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

Lee, Kwan Ho = 探討網絡上的若干動態過程 / 李鈞浩. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 114-118). / Abstracts in English and Chinese. / Lee, Kwan Ho = Tan tao wang luo shang de ruo gan dong tai guo cheng / Li Junhao. / Chapter 1 --- Overview --- p.1 / Chapter 2 --- Networks --- p.5 / Chapter 2.1 --- Describing Networks --- p.5 / Chapter 2.1.1 --- Adjacency Matrix --- p.6 / Chapter 2.1.2 --- "Degree, Degree Distribution and Mean Degree" --- p.6 / Chapter 2.1.3 --- Clustering Coefficient --- p.7 / Chapter 2.1.4 --- "Shortest Path, Shortest Distance and Diameter" --- p.7 / Chapter 2.1.5 --- Betweenness --- p.9 / Chapter 2.2 --- Barabasi-Albert (BA) Network --- p.10 / Chapter 2.2.1 --- Construction of BA Network --- p.10 / Chapter 2.2.2 --- Analytical Study of Degree Distribution --- p.11 / Chapter 2.2.3 --- Numerical Study of Degree Distribution --- p.12 / Chapter 2.2.4 --- Shortest Distance --- p.13 / Chapter 2.3 --- Summary --- p.14 / Chapter 3 --- Routing in Networks: A Review --- p.16 / Chapter 3.1 --- Introduction --- p.16 / Chapter 3.2 --- Dijkstra´ةs Algorithm --- p.17 / Chapter 3.2.1 --- Algorithm --- p.17 / Chapter 3.2.2 --- Running Time --- p.18 / Chapter 3.2.3 --- Routing Table Based on Shortest Path Algorithm --- p.19 / Chapter 3.3 --- Routing Model --- p.19 / Chapter 3.3.1 --- General Setup --- p.19 / Chapter 3.3.2 --- Phase Transition and Evaluation of Network Performance --- p.20 / Chapter 3.4 --- Using Shortest Path as Routing Algorithm on BA Networks --- p.21 / Chapter 3.5 --- Other Routing Algorithms --- p.22 / Chapter 3.5.1 --- Efficient Path --- p.23 / Chapter 3.5.2 --- Routing based on Local Structural Information --- p.24 / Chapter 3.5.3 --- Routing based on Dynamical Information --- p.25 / Chapter 3.6 --- Summary --- p.26 / Chapter 4 --- Optimization of Routing Efficiency through Redistributing Limited Resources --- p.28 / Chapter 4.1 --- A Reallocation Rule - Short to Long (S2L) --- p.29 / Chapter 4.2 --- Performance Enhancement After Applying S2L --- p.33 / Chapter 4.3 --- Optimized Capability Distribution in Detail --- p.36 / Chapter 4.4 --- Summary --- p.44 / Chapter 5 --- N-person Evolutionary Snowdrift Game: A Review --- p.47 / Chapter 5.1 --- Snowdrift Game (SG) and Evolutionary Snowdrift Game (ESG) --- p.47 / Chapter 5.2 --- N-person Evolutionary Snowdrift Game --- p.49 / Chapter 5.2.1 --- Payoffs of C-character and D-character Agents --- p.49 / Chapter 5.2.2 --- Replicator Dynamics --- p.50 / Chapter 5.2.3 --- Numerical Simulations --- p.52 / Chapter 5.3 --- Summary --- p.55 / Chapter 6 --- NESG on Complex Network --- p.56 / Chapter 6.1 --- Models --- p.57 / Chapter 6.2 --- Results of Model A (varying N) --- p.58 / Chapter 6.2.1 --- Correlation of Characters in Degree --- p.60 / Chapter 6.2.2 --- Correlation of Characters in Distance --- p.62 / Chapter 6.3 --- Results of Model B (Fixed-N) --- p.63 / Chapter 6.3.1 --- Correlation of Characters in Degree --- p.64 / Chapter 6.4 --- Summary --- p.69 / Chapter 7 --- Synchronization: A Review --- p.71 / Chapter 7.1 --- Kuramoto Model --- p.72 / Chapter 7.1.1 --- Analytical Method --- p.74 / Chapter 7.1.2 --- Numerical Method --- p.78 / Chapter 7.1.3 --- Summary of Kuramoto Model --- p.81 / Chapter 7.2 --- Integrate-and-Fire Model --- p.81 / Chapter 8 --- Kuramoto Model with Spatially Distributed Oscillators --- p.84 / Chapter 8.1 --- Model --- p.84 / Chapter 8.2 --- Numerical Results --- p.85 / Chapter 8.3 --- Analytic Results --- p.87 / Chapter 8.4 --- Summary --- p.90 / Chapter 9 --- Integrate-Fire-and-Run Model --- p.92 / Chapter 9.1 --- Model --- p.92 / Chapter 9.2 --- Two-Body System --- p.94 / Chapter 9.2.1 --- Case I: Oscillators A and B are in different sites --- p.94 / Chapter 9.2.2 --- Case II: Oscillators A and B are in the same site --- p.101 / Chapter 9.2.3 --- Comparison of Analytic Results and Numerical Simulations of Two-Body system --- p.103 / Chapter 9.3 --- N-Body System --- p.105 / Chapter 9.4 --- Summary --- p.111 / Chapter 10 --- Outlook --- p.112 / Bibliography --- p.114

As dificuldades no aprendizado da leitura podem ter uma causa neurológica ocasionada por fatores genéticos ou ambientais. O presente trabalho integra modelos matemáticos e neurocientíficos acerca dos processos neurais responsáveis pela leitura para estudar a dinâmica cerebral de alunos com e sem dificuldades no aprendizado da leitura. Utiliza-se, nesse estudo, uma técnica de mapeamento cerebral que considera o cérebro como uma rede complexa, onde os neurônios de diversas áreas cerebrais podem se organizar em subredes permitindo a execução paralela de diversos processos neurais. Mostra-se que os agrupamentos das áreas cerebrais de ambos os grupos, obtidos através de análise fatorial, são condizentes com modelos correntes em neurociências que sugerem para a leitura duas possíveis vias neurais, além do envolvimento de componentes de controle atencional (funções executivas). / Reading learning difficulties can be caused by genetic or environmental factors. The present work integrate graph theory and models from neuroscience about the neurological processes involved in reading to study the cerebral dynamics of children with and without learning difficulties. The brain mapping technique used in the present study, considers the brain as a complex network where neurons from several areas can be organized on sub-networks allowing a parallel execution of several neural processes. It is shown that the brain areas associations disclosed by factorial analysis, are congruent with the neuroscientific models that consider the existence of two possible neurological routes involved in reading besides the participation of the executive functions.

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of: (1) a single cycle of length v, (2) f fixed points and a cycle of length v − f, or (3) two disjoint cycles. The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.

There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.