Thesis (M.S.)--Rochester Institute of Technology, 1989. / References: leaves 34-37.

Thesis (M.Sc.)--University of Guelph (Canada), 2002. / Advisers: Tom Wilson, Gary Grewal. Includes bibliographical references.

Thesis (M.S.)--Georgia State University, 2006. / Title from title screen. Alexander Zelikovsky, committee chair; Anu Bourgeois, Saeid Belkasim, committee members. Electronic text (59 p. : ill. (some col.)) : digital, PDF file. Description based on contents viewed June 28, 2007. Includes bibliographical references (p. 58-59).

Li, Liang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Partitioning --- p.1 / Chapter 1.1.2 --- Floorplanning and Placement --- p.2 / Chapter 1.1.3 --- Routing --- p.2 / Chapter 1.1.4 --- Compaction --- p.3 / Chapter 1.2 --- Motivations --- p.3 / Chapter 1.3 --- Problem Formulation --- p.4 / Chapter 1.3.1 --- Properties of OARSMT --- p.4 / Chapter 1.4 --- Progress on the Problem --- p.4 / Chapter 1.5 --- Contributions --- p.5 / Chapter 1.6 --- Thesis Organization --- p.6 / Chapter 2 --- Literature Review on OARSMT --- p.8 / Chapter 2.1 --- Introduction --- p.8 / Chapter 2.2 --- Previous Methods --- p.9 / Chapter 2.2.1 --- OARSMT --- p.9 / Chapter 2.2.2 --- Shortest Path Problem with Blockages --- p.13 / Chapter 2.2.3 --- OARSMT with Delay Minimization --- p.14 / Chapter 2.2.4 --- OARSMT with Worst Negative Slack Maximization --- p.14 / Chapter 2.3 --- Comparison --- p.15 / Chapter 3 --- Heuristic Method --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.2 --- Our Approach --- p.18 / Chapter 3.2.1 --- Handling of Multi-pin Nets --- p.18 / Chapter 3.2.2 --- Propagation --- p.20 / Chapter 3.2.3 --- Backtrack --- p.23 / Chapter 3.2.4 --- Finding MST --- p.26 / Chapter 3.2.5 --- Local Refinement Scheme --- p.26 / Chapter 3.3 --- Experimental Results --- p.28 / Chapter 3.4 --- Summary --- p.28 / Chapter 4 --- Exact Method --- p.32 / Chapter 4.1 --- Introduction --- p.32 / Chapter 4.2 --- Review on GeoSteiner --- p.33 / Chapter 4.3 --- Overview of our Approach --- p.33 / Chapter 4.4 --- FST with Virtual Pins --- p.34 / Chapter 4.4.1 --- Definition of FST --- p.34 / Chapter 4.4.2 --- Notations --- p.36 / Chapter 4.4.3 --- Properties of FST with Virtual Pins --- p.36 / Chapter 4.5 --- Generation of FST with Virtual Pins --- p.46 / Chapter 4.5.1 --- Generation of FST with Two Pins --- p.46 / Chapter 4.5.2 --- Generation of FST with 3 or More Pins --- p.48 / Chapter 4.6 --- Concatenation of FSTs with Virtual Pins --- p.50 / Chapter 4.7 --- Experimental Results --- p.52 / Chapter 4.8 --- Summary --- p.53 / Chapter 5 --- Conclusion --- p.55 / Bibliography --- p.61

No description available.

Thesis (Ph.D.)--McMaster University (Canada), 1995. / Source: Dissertation Abstracts International, Volume: 57-03, Section: B, page: 2045. Adviser: T. Jiang.

S(5,8,24) is one of the largest known Steiner systems and connects combinatorial designs, error-correcting codes, finite simple groups, and sphere packings in a truly remarkable way. This thesis discusses the underlying structure of S(5,8,24), its construction via the (24,12) Golay code, as well its automorphism group, which is the Mathieu group M24, a member of the sporadic simple groups. Particular attention is paid to the calculation of the size of automorphism groups of Steiner systems using the Orbit-Stabilizer Theorem. We conclude with a section on the sphere packing problem and elaborate on how the 8-sets of S(5,8,24) can be used to form Leech's Lattice, which Leech used to create the densest known sphere packing in 24-dimensions. The appendix contains code written for Matlab which has the ability to construct the octads of S(5,8,24), permute the elements to obtain isomorphic S(5,8,24) systems, and search for certain subsets of elements within the octads. / Master of Science

In this dissertation, we study some open problems concerning the existence or non-existence of some combinatorial designs. We give the construction or proof of non-existence of some Steiner systems, large sets of designs, and graph designs, with prescribed automorphism groups. / by Emre Kolotoæglu. / Thesis (Ph.D.)--Florida Atlantic University, 2013. / Includes bibliography. / Mode of access: World Wide Web. / System requirements: Adobe Reader.

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

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.