Search

An H-design H(v, g, k, t) is a triple (X , G , B) , where X is a set of gv points, G is a partition of X into v disjoint groups of size g, and B is a set of G -transverse k-subsets, called blocks, such that each G -transverse t-subset is contained in exactly one block of B . A frame-derived H-design FDH(v, g, 4, 3) is an H(v, g, 4, 3) whose derived design at every point forms a Kirkman frame, an H (v - 1 , g , 3 , 2) having a resolution into g (v - 1) / 2 holey parallel classes. FDH(v, g, 4, 3)s are proved to be effective designs to produce large sets of Kirkman triple systems (LKTS) in this paper. Related recursive constructions are established and direct constructions for FDH(v, 2, 4, 3)s are displayed by using automorphism groups. The existence result on LKTS is improved as well. [ABSTRACT FROM AUTHOR]

For k ⩾ 4, a loose k-cycle Ck is a hypergraph with distinct edges e1, e2, ..., ek such that consecutive edges (modulo k) intersect in exactly one vertex and all other pairs of edges are disjoint. Our main result is that for every even integer k ⩾ 4, there exists c > 0 such that the number of triple systems with vertex set [n] containing no Ck is at most 2 c n 2 . An easy construction shows that the exponent is sharp in order of magnitude. Our proof method is different than that used for most recent results of a similar flavor about enumerating discrete structures, since it does not use hypergraph containers. One novel ingredient is the use of some (new) quantitative estimates for an asymmetric version of the bipartite canonical Ramsey theorem. [ABSTRACT FROM AUTHOR]

To every Steiner system with parameters (t,k,v) on {1,...,v} and blocks B, we can assign its characteristic vector χB, which is a (0,1)‐vector whose entries are indexed by the k‐subsets of {1,...,v} such that for each k‐subset A of {1,...,v},χB(A)=1 if and only if A∈B. In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters (t,k,v) is (vk)−(vt)+1, provided that 1≤t≤k≤v/2 and there is at least one such system. [ABSTRACT FROM AUTHOR]

We introduce two monads on the category of graphs and prove that their Eilenberg- Moore categories are isomorphic to the category of perfect matchings and the category of partial Steiner triple systems, respectively. As a simple application of these results, we describe the product in the categories of perfect matchings and partial Steiner triple systems. [ABSTRACT FROM AUTHOR]

We show that the maximum number of triples on n points, if no three triples span at most five points, is (1±o(1))n2/5. More generally, let f(r)(n;k,s) be the maximum number of edges in an r‐uniform hypergraph on n vertices not containing a subgraph with k vertices and s edges. In 1973, Brown, Erdős and Sós conjectured that the limit limn→∞n−2f(3)(n;k,k−2) exists for all k. They proved this for k=4, where the limit is 1/6 and the extremal examples are Steiner triple systems. We prove the conjecture for k=5 and show that the limit is 1/5. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate H‐decompositions of Kn for a suitably defined graph H. [ABSTRACT FROM AUTHOR]

We show that there are exactly 2624 isomorphism classes of Steiner triple systems on 27 points having 3-rank 24, all of which are actually resolvable. More generally, all Steiner triple systems on 3n points having 3-rank at most 3n-n are resolvable. Combining this observation with the lower bound on the number of such STS(3n) recently established by two of the present authors, we obtain a strong lower bound on the number of Kirkman triple systems on 3n points. For instance, there are more than 1099 isomorphism classes of KTS(81). [ABSTRACT FROM AUTHOR]

A μ-way (v, k, t) trade is a pair T=(X,{T1,T2,...,Tμ}) such that for eacht-subset of v-set X the number of blocks containing this t-subset is the same in each Ti(1≤i≤μ). In the other words for each 1≤i

The purpose of this article is to show the link between Jordan quadruple systems with quadripotents and Jordan algebras. We also extend the notions of the orthogonality, primitivity, and minimality of tripotents in a Jordan triple system to that of quadripotents in a Jordan quadruple system. We refine the Peirce decomposition of a Jordan quadruple system with respect to a quadripotent to be with respect to a system of orthogonal quadripotents and get the multiplication rules of the Peirce spaces. We show that the notions of primitive and minimal quadripotents coincide in a Jordan quadruple system. [ABSTRACT FROM AUTHOR]

In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of k-restricted full components for some k ≥ 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for k → ∞. However, the running time is also exponentially dependent on k, so only small k are tractable in practice. We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact algorithm based on integer linear programs, and to fast and simple 2-approximations as well as state-of-the-art heuristics. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the following question: given an arbitrary Steiner triple system S on m vertices and any 3‐uniform hypertree T on n vertices, is it necessary that S contains T as a subgraph provided m≥(1+μ)n? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive. [ABSTRACT FROM AUTHOR]

An H(m,g,k,3) design is a triple (X,T,B), where X is a set of mg points, T a partition of X into m disjoint sets of size g, and B a set of k‐element transverses of T, such that each 3‐element transverse of T is contained in exactly one of them. In 1990, Mills determined the existence of an H(m,g,4,3) design with m≠5. In this paper, an efficient construction shows that an H(5,g,4,3) exists for any integer g≡2,10(mod12) with g≥10. Consequently, the necessary and sufficient conditions for the existence of an H(m,g,4,3) design are m≥4, mg≡0(mod2), and g(m−1)(m−2)(mod3), with a definite exception (m,g)=(5,2). [ABSTRACT FROM AUTHOR]

NU Ori is a massive spectroscopic and visual binary in the Orion Nebula Cluster, with four components: Aa, Ab, B, and C. The B0.5 primary (Aa) is one of the most massive B-type stars reported to host a magnetic field. We report the detection of a spectroscopic contribution from the C component in high-resolution ESPaDOnS spectra, which is also detected in a Very Large Telescope Interferometer data set. Radial velocity (RV) measurements of the inner binary (designated Aab) yield an orbital period of 14.3027(7) d. The orbit of the third component (designated C) was constrained using both RVs and interferometry. We find C to be on a mildly eccentric 476(1) d orbit. Thanks to spectral disentangling of mean line profiles obtained via least-squares deconvolution, we show that the Zeeman Stokes V signature is clearly associated with C, rather than Aa as previously assumed. The physical parameters of the stars were constrained using both orbital and evolutionary models, yielding M Aa = 14.9 ± 0.5 M⊙, M Ab = 3.9 ± 0.7 M⊙, and M C = 7.8 ± 0.7 M⊙. The rotational period obtained from longitudinal magnetic field 〈 B |$z$| 〉 measurements is P rot = 1.09468(7) d, consistent with previous results. Modelling of 〈 B |$z$| 〉 indicates a surface dipole magnetic field strength of ∼8 kG. NU Ori C has a magnetic field strength, rotational velocity, and luminosity similar to many other stars exhibiting magnetospheric Hα emission, and we find marginal evidence of emission at the expected level (∼1 per cent of the continuum). [ABSTRACT FROM AUTHOR]

We present a new exact algorithm for computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2‐edge‐connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2‐edge‐connected Steiner network problem. [ABSTRACT FROM AUTHOR]

A Berge-K4 in a triple system is a configuration with four vertices v1, v2, v3, v4 and six distinct triples {eij: 1 ≤ i < j ≤ 4} such that{ui, vj}⊂ eij for every 1 ≤ i < j ≤ 4. We denote by B the set of Berge-K4 configurations. A triple system is B -free if it does not contain any member of B . We prove that the maximum number of triples in a B -free triple system on n ≥ 6 points is obtained by the balanced complete 3-partite triple system: all triples {abc: a ϵ A, b ϵ B, c ϵ C} where A,B,C is a partition of n points with [n/3]= |A| ≤|B| ≤ |C| = n/33 [ABSTRACT FROM AUTHOR]

Bruck constructed the first prolongation and contraction of quasigroups in order to study Steiner triple systems. In this paper we define a new family of quasigroups: The Steiner- Bruck quasigroups (SB-quasigroups), where aa2 = a2a and a2 = b2 for all possible a and b, which arise from Bruck's prolongation. We use Bruck's prolongation and contraction maps to explore properties of this family of quasigroups. Among other results, we show that there is a one-to-one correspondence between SB-quasigroups and uniquely 2-divisible quasigroups. As a corollary to this result we find a correspondence between idempotent quasigroups and loops of exponent 2. We then use this correspondence to study some interesting loops of exponent two and some interesting idempotent quasigroups. [ABSTRACT FROM AUTHOR]

We describe Steiner loops of nilpotency class 2 and establish the classification of finite 3-generated nilpotent Steiner loops of nilpotency class 2. [ABSTRACT FROM AUTHOR]

This paper presents a novel method to determine the optimal routing of medium voltage distribution networks in sparse rural areas. The objective is evaluated through minimizing the net present cost of the network over a selected time period. A problem specific genetic algorithm is proposed to address the optimal network routing problem and compute the optimized topology throughout a geographically constrained region. The proposed method simultaneously considers nonfixed candidate lines to overcome search space restrictions through a variable length encoding structure and the use of Steiner points, and a shortest path algorithm to traverse between point-to-point connections in the constrained region. Geographical restrictions on network routing are considered through the formation of a rasterized map. The network is modeled at the branch level and considers both greenfield and expansion planning to highlight the effects of accessibility restrictions. The optimization model is applied to a real rural distribution network in the South–West of Western Australia. Alternative network topologies are found to provide significant improvements over the existing network and traditional reconfiguration based methods for evaluating the minimum cost sparse rural distribution network. [ABSTRACT FROM AUTHOR]

By the von Neumann inequality for homogeneous polynomials there exists a positive constant C k , q C_{k,q} (n) such that for every k-homogeneous polynomial p in n variables and every n-tuple of commuting operators ( T 1 T_{1} ,..., T n T_{n}) with ∑ i = 1 n ∥ T i ∥ q ≤ 1 {\sum_{i=1}^{n}\|T_{i}\|^{q}\leq 1} we have ∥ p ⁢ (T 1 , ... , T n) ∥ ℒ ⁢ (ℋ) ≤ C k , q ⁢ (n) ⁢ sup ⁡ { | p ⁢ (z 1 , ... , z n) | : ∑ i = 1 n | z i | q ≤ 1 } . \|p(T_{1},\ldots,T_{n})\|_{\mathcal{L}(\mathcal{H})}\leq C_{k,q}(n)\sup\Biggl{% \{}|p(z_{1},\ldots,z_{n})|:\sum_{i=1}^{n}|z_{i}|^{q}\leq 1\Biggr{\}}. For fixed k and q, we study the asymptotic growth of the smallest constant C k , q C_{k,q} (n) as n (the number of variables/operators) tends to infinity. For q = ∞ \infty , we obtain the correct asymptotic behavior of this constant (answering a question posed by Dixon in the 1970s). For 2 ≤ \leq q < < ∞ \infty we improve some lower bounds given by Mantero and Tonge, and prove the asymptotic behavior up to a logarithmic factor. To achieve this we provide estimates of the norm of homogeneous unimodular Steiner polynomials, i.e. polynomials such that the multi-indices corresponding to the nonzero coefficients form partial Steiner systems. [ABSTRACT FROM AUTHOR]

A decomposition of the blocks of an STS(v) into partial parallel classes of size m is equivalent to a Kirkman signal set KSS(v,m). We give decompositions of STS(4v-3) into classes of size v-1 when v≡3(mod6), v≠3. We also give decompositions of STS(v) into classes of various sizes when v is a product of two arbitrary integers that are both congruent to 3(mod6). These results produce new families of KSS(v,m). [ABSTRACT FROM AUTHOR]

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F ⊆ E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and |E(T)|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and that has size polynomial in |C|. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w(f), and an accuracy parameter ε > 0, uncovers a set F ⊆ E(G) of total weight at most poly(ε-1) w(f) that, for any set of terminal pairs that lie on f, contains a Steiner forest within additive error ε w(f) from the optimal Steiner forest. [ABSTRACT FROM AUTHOR]

Codebooks with low-coherence have wide utilization in many fields, such as direct spread code division multiple access communications, compressed sensing and so on. There are two major ingredients in this paper. The first is to present a new character sum, the hyper Eisenstein sum and study the properties of this character sum. As an application, the second ingredient is to propose two constructions of codebooks with the hyper Eisenstein sum. The codebooks generated by these constructions asymptotically meet the Welch bound. The parameters of these codebooks are new. [ABSTRACT FROM AUTHOR]

This article presents an approximation algorithm for the Steiner connectivity problem, which is a generalization of the Steiner tree problem that involves paths instead of edges. The problem can also be seen as hypergraph‐version of the Steiner tree problem; it arises in line planning in public transport. We prove a k + 1 approximation guarantee, where k is the minimum of the maximum number of nodes in a path minus 1 and the maximum number of terminal nodes in a path. The result is based on a structural degree property for terminal nodes. [ABSTRACT FROM AUTHOR]

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon. [ABSTRACT FROM AUTHOR]

The article analyzes the Steiner approach to cephalometric theory and technique. Cephalometrics, as stated, has five aspects including, it radiologically studies cranio-facial structures, it determines dento-facial growth trends and potentials, and it determines diagnostically appropriate therapy. It is stated that, cephalometrics is an important clinical diagnostic tool for the dentist and other office personnel. Cephalometrics, as reported, has several major treatment benefits including, demonstration of beneficial growth trends using established age norms for comparison, reinforcement of clinical judgment made during routine examination, and definition of the form and pace of dental treatment through prediction of dental needs, eruptive problems, and structural faults.

Some relations between finite geometric spaces and cooperative games are considered. The games associated to Steiner systems, in particular projective and affine planes, are considered. The properties of winning and blocking coalitions are investigated.

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs. [ABSTRACT FROM AUTHOR]

This work presents a recursive construction for simple t-designs using resolutions of the ingredient designs. The result extends a construction of t-designs in our recent paper van Trung (Des Codes Cryptogr 83:493-502, 2017). Essentially, the method in van Trung (Des Codes Cryptogr 83:493-502, 2017) describes the blocks of a constructed design as a collection of block unions from a number of appropriate pairs of disjoint ingredient designs. Now, if some pairs of these ingredient t-designs have both suitable s-resolutions, then we can define a distance mapping on their resolution classes. Using this mapping enables us to have more possibilities for forming blocks from those pairs. The method makes it possible for constructing many new simple t-designs. We give some application results of the new construction. [ABSTRACT FROM AUTHOR]

A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances. The effectiveness of our method is compared in an extensive computational study with the state-of-the-art exact approach, which employs a Benders decomposition based on two-stage branch-and-cut, and a genetic algorithm introduced during the DIMACS implementation challenge on Steiner trees. Our results indicate that the presented method significantly outperforms existing ones, both on benchmark instances from literature, as well as on large-scale telecommunication networks. [ABSTRACT FROM AUTHOR]

Abstract: Given a combinatorial design D with block set B, the block‐intersection graph (BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | > 0. The i‐block‐intersection graph (i‐BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | = i. In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes. [ABSTRACT FROM AUTHOR]

In this paper, we give some properties of the generalized derivation algebra GDer(T) of a Hom-Lie triple systems T. In particular, we prove that GDer(T)=QDer(T)+QC(T), the sum of the quasiderivation algebra and the quasicentroid. We also prove that QDer(T) can be embedded as derivations in a larger Hom-Lie triple system. General results on centroids of Hom-Lie triple systems are also developed in this paper. [ABSTRACT FROM AUTHOR]

In this paper we prove some bounds for Steiner distance in Cartesian product. We investigate properties of connected subgraphs that are not Steiner convex. Those results are the key in the characterization of Steiner convex sets of grids and also in the characterization of 3-Steiner convex sets of Cartesian product graphs. [ABSTRACT FROM AUTHOR]

We show that for any 1 ≤ p ≤ ∞, the family of random vectors uniformly distributed on hyperplane projections of the unit ball of lpn verify the variance conjecture Var ∣X∣2 ≤ C max ξ∈Sn-1 E2 E∣X∣2, where C depends on p but not on the dimension n or the hyperplane. We will also show a general result relating the variance conjecture for a random vector uniformly distributed on an isotropic convex body and the variance conjecture for a random vector uniformly distributed on any Steiner symmetrization of it. As a consequence we will have that the class of random vectors uniformly distributed on any Steiner symmetrization of an lpn -ball verify the variance conjecture. [ABSTRACT FROM AUTHOR]

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and , the Steiner distance dG(S) among the vertices of S is the minimum size among all connected subgraphs whose vertex sets contain S. Let n, k be two integers with 2 ≤ k ≤ n. Then the Steiner k-eccentricity ek(v) of a vertex v of G is defined by . Furthermore, the Steiner k-diameter of G is . In 2011, Chartrand, Okamoto and Zhang showed that k − 1 ≤ sdiamk(G) ≤ n − 1. In this paper, graphs with sdiam4( G) = 3, 4, n − 1 are characterized, respectively. [ABSTRACT FROM AUTHOR]

Abstract: Steiner systems are a fascinating topic of combinatorics. The most studied Steiner systems are S ( 2 , 3 , v ) (Steiner triple systems), S ( 3 , 4 , v ) (Steiner quadruple systems), and S ( 2 , 4 , v ). There are a few infinite families of Steiner systems S ( 2 , 4 , v ) in the literature. The objective of this paper is to present an infinite family of Steiner systems S ( 2 , 4 , 2 m ) for all m ≡ 2 ( mod 4 ) ≥ 6 from cyclic codes. As a by‐product, many infinite families of 2‐designs are also reported in this paper. [ABSTRACT FROM AUTHOR]

A famous result of Bonisoli characterizes the equidistant linear codes over GF(q) (up to monomial equivalence) as replications of some q-ary simplex code, possibly with added 0-coordinates. We first prove a variation of this theorem which characterizes the replications of first order generalized Reed–Muller codes among the two-weight linear codes. In the second part of this paper, we use Bonisoli’s theorem and our variation to study the linear block codes of Steiner triple systems, which can only be non-trivial in the binary and ternary case. Assmus proved that the block by point incidence matrices of all Steiner triple systems on v points which have the same 2-rank generate equivalent binary codes and gave an explicit description of a generator matrix for such a code. We provide an alternative, considerably simpler, proof for these results by constructing parity check matrices for the binary codes spanned by the incidence matrix of a Steiner triple system instead, and we also obtain analogues for the ternary case. Moreover, we give simple alternative coding theoretical proofs for the lower bounds of Doyen, Hubaut and Vandensavel on the 2- and 3-ranks of Steiner triple systems. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) are communication networks having tiny sensors with sensing and transmitting capabilities. These systems adopting traditional routing protocols to organize communication, have design issues, and quality of service is still a challenging research factor. The key idea of this research is to discover the most efficient routing protocols based on the design of a reliable and efficient routing protocol to determine quality of services in a WSN. In this paper we propose a reliable and efficient path selection strategy by designing a Quality of Service Aware multicast routing protocol. This protocol discusses the multicast routing problem of WSN with multiple QoS constraints, by discovering a minimum resource consumption path while satisfying multiple constraints optimization conditions. Simulation results show that the fair link selection strategy can yield to a good solution for this traditionally NP complex problem, as compared to the best multicast algorithms known. [ABSTRACT FROM AUTHOR]

It is proved that for a convex body with C2 boundary and positive Gauss curvature, its Steiner symmetral is again a convex body with C2 boundary and positive Gauss curvature. [ABSTRACT FROM AUTHOR]

We investigate Steiner's Porism in finite MiquelianMöbius planes constructed over the pair of finite fields GF(q) and GF(q²), for an odd prime power q. Properties of common tangent circles for two given concentric circles are discussed and with that, a finite version of Steiner's Porism for concentric circles is stated and proved. We formulate conditions on the length of a Steiner chain by using the quadratic residue theorem in GF(q). These results are then generalized to an arbitrary pair of non-intersecting circles by introducing the notion of capacitance, which turns out to be invariant under Möbius transformations. Finally, the results are compared with the situation in the classical Euclidean plane. [ABSTRACT FROM AUTHOR]

We call a partial Steiner triple system C (configuration) t-Ramsey if for large enough n (in terms of [ABSTRACT FROM AUTHOR]

The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime O(r(r + s - 1) · wmax ), where r, s, and wmax are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph.We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance. [ABSTRACT FROM AUTHOR]

In this article, it is shown that there is a partitioning of the set of 3-arcs in a projective plane of order three into nine pairwise disjoint Steiner triple systems of order 13. [ABSTRACT FROM AUTHOR]

Research on the existence of large sets of Kirkman triple systems (LKTS) extends from the mid-eighteen hundreds to the present. Enlightened by known direct constructions of LKTSs, we bring forth new approaches and finally establish the existence of LKTSs of all admissible prime power sizes less than 400 only with two possible exceptions. In the process, we also employ known construction methods and draw support from efficient algorithms. [ABSTRACT FROM AUTHOR]

Given a graph $G$ and a set $Q$ of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS) problem. The SMCS, or $G$ 's induced subgraph that contains $Q$ with the largest connectivity, can be useful for customer prediction, product promotion, and team assembling. Despite its importance, the SMCS problem has only been recently studied. Existing solutions evaluate the maximum SMCS, whose number of nodes is the largest among all the SMCSs of $Q$ . However, the maximum SMCS, which may contain a lot of nodes, can be difficult to interpret. In this paper, we investigate the minimal SMCS , which is the minimal subgraph of $G$ with the maximum connectivity containing $Q$ . The minimal SMCS contains much fewer nodes than its maximum counterpart, and is thus easier to be understood. However, the minimal SMCS can be costly to evaluate. We thus propose efficient Expand-Refine algorithms, as well as their approximate versions with accuracy guarantees. We further develop a cache-based processing model to improve the efficiency for an important case when $Q$ consists of a single node. Extensive experiments on large real and synthetic graph datasets validate the effectiveness and efficiency of our approaches. [ABSTRACT FROM PUBLISHER]

We consider the tetrahedral subdivision problem for a polygonal prismatic mesh with prescribed boundary constraints and without Steiner points. We prove the necessary and sufficient conditions for the existence of solutions, and also provide algorithms to compute such a constrained subdivision if there exists one. The result applies to arbitrary k-gonal prismatic meshes and even mixed prismatic meshes, allowing arbitrary topology for the base mesh and arbitrary constraints on the boundary. [ABSTRACT FROM AUTHOR]

It is well known that given a Steiner triple system (STS) one can define a binary operation * upon its base set by assigning x * x = x for all x and x * y = z, where z is the third point in the block containing the pair {x, y}. The same can be done for Mendelsohn triple systems (MTS), directed triple systems (DTS) as well as hybrid triple systems (HTS), where (x, y) is considered to be ordered. In the case of STSs and MTSs the operation yields a quasigroup, however this is not necessarily the case for DTSs and HTSs. A DTS or an HTS which induces a quasigroup is said to be Latin. In this paper we study Latin DTSs and Latin HTSs which admit a cyclic or a 1-rotational automorphism. We prove the existence spectra for these systems as well as the existence spectra for their pure variants. As a side result we also obtain the existence spectra of pure cyclic and pure 1-rotational MTSs. [ABSTRACT FROM AUTHOR]

Connectivity has significance in both of data collection and aggregation for Wireless Sensor Networks (WSNs). Once the connectivity is lost, relay nodes are deployed to build a Steiner Minimal Tree (SMT) such that the inter-component connection is reestablished. In recent years, there has been a growing interest in connectivity restoration problems. In previous works, the deployment area of a WSN is assumed to be flat without obstacles. However, such an assumption is not realistic. In addition, most of the existing strategies chose the representative of each component, which serves as the starting point of relay node deployment during the connectivity restoration, either in a random way or in the shortest-distance based manner. In fact, both ways of representative selection could potentially increase the length of the SMT such that more relay nodes are required. In this paper, a novel connectivity restoration strategy is proposed--Obstacle-Avoid connectivity restoration strategy based on Straight Skeletons (OASS), which employs both the polygon based representative selection with the presence of obstacles and the straight skeleton based SMT establishment. The OASS is proved to be a 3-opt approximation algorithm with the complexity of O(n log n), and the approximation ratio can reduce to 3 p 3 2 while it satisfies a certain condition. The theoretical analysis and simulations show that the performance of the OASS is better than other strategies in terms of the relay count and the quality of the established topology (i.e., distances between components, delivery latency and balanced traffic load) as well. [ABSTRACT FROM AUTHOR]

This study is concerned with a novel Monte Carlo Tree Search algorithm for the problem of minimal Euclidean Steiner tree on a plane. Given p points (terminals) on a plane, the goal is to find a connection between all the points, so that the total sum of the lengths of edges is as low as possible, while an addition of extra points (Steiner points) is allowed. Finding the minimum Steiner tree is known to be np-hard. While exact algorithms exist for this problem in 2D, their efficiency decreases when the number of terminals grows. A novel algorithm based on Upper Conffidence Bound for Trees is proposed. It is adapted to the specifficfficharacteristics of Steiner trees. A simple heuristic for fast generation of feasible solutions based on Fermat points is proposed together with a correction procedure. By combing Monte Carlo Tree Search and the proposed heuristics, the proposed algorithm is shown to work better than both the greedy heuristic and pure Monte Carlo simulations. Results of numerical experiments for randomly generated and benchmark library problems (from OR-Lib) are presented and discussed. [ABSTRACT FROM AUTHOR]

Let Σ = (X, B) be a 6-cycle system of order v, so v = 1, 9 mod 12. A c-colouring of type s is a map φ B → C, with C set of colours, such that exactly c colours are used and for every vertex x all the blocks containing x are coloured exactly with s colours. Let v-1/2 = qs + r, with q, r ≥ 0. φ is equitable if for every vertex x the set of the v-1/2 blocks containing x is partitioned in r colour classes of cardinality q + 1 and s - r colour classes of cardinality q. In this paper we study bicolourings and tricolourings, for which, respectively, s = 2 and s = 3, distinguishing the cases v = 12k+1 and v = 12k+9. In particular, we settle completely the case of s = 2, while for s = 3 we determine upper and lower bounds for c. [ABSTRACT FROM AUTHOR]

Two resolutions of the same $$\hbox {SQS}(v)$$ are said to be orthogonal, when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. If an $$\hbox {SQS}(v)$$ has two orthogonal resolutions, the $$\hbox {SQS}(v)$$ is called a doubly resolvable $$\hbox {SQS}(v)$$ . In this paper, we use a quadrupling construction to obtain an infinite class of doubly resolvable Steiner quadruple systems. We also give some results of doubly resolvable H designs and doubly resolvable candelabra quadruple systems. [ABSTRACT FROM AUTHOR]