Search

Abstract: In this short survey, some approaches that can be used to solve the generalized -design problem are considered. Special cases of the generalized -design problem include well-known conjectures for -designs, degree sequences of graphs and hypergraphs, and partial Steiner systems. Also described are some related problems such as the characterization of -vectors of pure simplicial complexes, which are well known but little understood. Some suggestions how enumerative and polyhedral techniques may help are also described. [Copyright &y& Elsevier]

Abstract: The geometric bottleneck Steiner network problem on a set of vertices embedded in a normed plane requires one to construct a graph spanning and a variable set of additional points, such that the length of the longest edge is minimised. If no other constraints are placed on , then a solution always exists which is a tree. In this paper, we consider the Euclidean bottleneck Steiner network problem for , where is constrained to be -connected. By taking advantage of relative neighbourhood graphs, Voronoi diagrams, and the tree structure of block cut-vertex decompositions of graphs, we produce exact algorithms of complexity and for the cases and respectively. Our algorithms can also be extended to other norms such as the planes. [Copyright &y& Elsevier]

Abstract: The Steiner problem in a -plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from uniform orientations in the plane. This network is referred to as a minimum -tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design. A -tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a -tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal -trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186–222]. For any path P in a -tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186–222]. [Copyright &y& Elsevier]