Search

The Steiner (k , k ′) -eccentricity of a given k ′ -subset of a graph G is the maximum Steiner distance over all k -subsets of V (G) which contain the given k ′ -subset, an extension of standard Steiner k -eccentricity. In this paper, we mainly study the Steiner (3 , 2) -eccentricity of trees. The σ -transformation which does not increase the average Steiner (3 , 2) -eccentricity is depicted. Using σ -transformation, several lower and upper bounds for the average Steiner (3 , 2) -eccentricity of trees are given. [ABSTRACT FROM AUTHOR]

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses with collinear triples (or alternatively, non-degenerate triangles) that coincide with the edges of a given 3-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that Steiner triple systems are not metric, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete 3-uniform hypergraph. The latter result was also generalized to pseudometric (almost-metric) betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest non-linear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles. [ABSTRACT FROM AUTHOR]

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph K n. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G , we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of K n. [ABSTRACT FROM AUTHOR]

In this article, we answer three questions from the paper (Das, 2021). We observe a tight lower bound for the triameter of trees in terms of order and number of leaves. We show that in a connected block graph any triametral triple of vertices contains a diametral pair and that any diametral pair of vertices can be extended to a triametral triple. We also present several open problems concerning the interplay between triametral triples, diametral pairs and peripheral vertices in median and distance-hereditary graphs. [ABSTRACT FROM AUTHOR]

The DB-GST problem is given an undirected graph G (V , E) , and a collection of groups S = { S i } i = 1 q , S i ⊆ V , find a tree that contains at least one vertex from every group S i , so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound d v , and every e ∈ E has a cost c (e) > 0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v , d e g T (v) ≤ d v , and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O (log 2 n) , O (log 2 n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O (log 2 n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O (log 2 n) , O (log 3 n)) (the approximation for the degrees is O (log 3 n)) ratio which is folklore. Getting O (log 2 n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al. (2016) that approximated the cost within O (log 2 n) , but did not approximate the degree. Our main result is an O (log 3 n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k -tree problem is given an undirected graph G (V , E) , a collection of terminals S ⊆ V , and a number k , find a tree T (V ′ , E ′) that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a ρ ratio approximation, then the DB-Steiner k -tree problem, admits an O (log 2 k ⋅ ρ) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to cover k / 4 of the groups with minimum maximal degree, then there is a deterministic O (log n ⋅ ρ) approximation for DB-Steiner k -tree problem. Using the work of Guo et al. (2020) we derive an O (log 3 n) approximation for DB-Steiner k -tree problem on general graphs, that runs in quasi-polynomial time. [ABSTRACT FROM AUTHOR]

The Steiner k -eccentricity of a vertex v of a graph G is the maximum Steiner distance over all k -subsets of V (G) which contain v. In this paper Steiner 3-eccentricity is studied on trees. Some general properties of the Steiner 3-eccentricity of trees are given. A tree transformation which does not increase the average Steiner 3-eccentricity is given. As its application, several lower and upper bounds for the average Steiner 3-eccentricity of trees are derived. [ABSTRACT FROM AUTHOR]

Techniques of producing new combinatorial structures from old ones are commonly called trades. The switching principle applies for a broad class of designs: it is a local transformation that modifies two columns of the incidence matrix. In this paper, we present a construction, which is a generalization of the switching transform for the class of Steiner 2-designs. We call this construction paramodification of Steiner 2-designs, since it modifies the parallelism of a subsystem. We study in more detail the paramodifications of affine planes, Steiner triple systems, and abstract unitals. Computational results show that paramodification can construct many new unitals. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G. A subtree T of G is an S -Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are internally disjoint (resp. edge-disjoint) if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S (resp. E (T 1) ∩ E (T 2) = 0̸). Let κ G (S) (resp. λ G (S)) be the maximum number of internally disjoint (resp. edge-disjoint) S -Steiner trees in G , and let κ k (G) (resp. λ k (G)) be the minimum κ G (S) (resp. λ G (S)) for S ranges over all k -subsets of V (G). It is well-known that the connectivity of the line graph of a graph G is closely related to the edge-connectivity of G. Chartrand et al., Li et al., and Li et al. showed that κ k (L (G)) ≥ λ k (G) for k = 2 , 3 , 4 , respectively. In [Discrete Math. 341(2018), 1945–1951.], Li et al. also proposed the following conjecture: κ k (L (G)) ≥ λ k (G) for integer k ≥ 2 and a graph G with at least k vertices. In this paper, we show that κ k (L (G)) ≥ λ k (G) − m a d (G) 2 2 for general k , where m a d (G) is the maximum average degree of a graph G. We also show that κ k (L (G)) ≥ λ k (G) − r 2 2 for any integers k and r such that k ≤ r 2 . Finally, we show that the conjecture holds for k = 5 , and the conjecture holds for the wheel graph and the complete bipartite graph K 3 , n. [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order p and S a nonempty set of vertices of G . Then the Steiner distance d ( S ) of S is the minimum size of a connected subgraph of G whose vertex set contains S . If n is an integer, 2 ≤ n ≤ p , the Steiner n -diameter, diam n ( G ) , of G is the maximum Steiner distance of any n -subset of vertices of G . This is a generalisation of the ordinary diameter, which is the case n = 2 . We give upper bounds on the Steiner n -diameter of maximum planar graphs in terms of order and connectivity. Moreover, we construct graphs to show that the bound is asymptotically sharp. Furthermore we extend this result to 4 and 5-connected maximal planar graphs. [ABSTRACT FROM AUTHOR]

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: Steiner 3-wise balanced designs are constructed for parameters 3-, 3-, 3-, 3-, 3-, where is a prime power and are integers. Further designs are obtained from these. [Copyright &y& Elsevier]

Abstract: Let be a directed/undirected graph, let , and let be an intersecting family on (that is, for any intersecting ) so that and for every . An edge set is an edge-cover of if for every there is an edge in from to . We show that minimal edge-covers of can be listed with polynomial delay, provided that, for any the minimal member of the residual family of the sets in not covered by can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal -connected and -outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time. [Copyright &y& Elsevier]

Abstract: A Steiner pentagon system of order is said to be super-simple if its underlying -BIBD is super-simple; that is, any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary condition for the existence of a super-simple ; namely, and or is sufficient, except for , and possibly for . In the process, we also improve an earlier result for the spectrum of super-simple -BIBDs, removing all the possible exceptions. We also give some new examples of Steiner pentagon packing and covering designs (SPPDs and SPCDs). [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]

Abstract: A study of the worst-case performance of Wong''s heuristic for the Steiner problem in directed networks (SPDN) is presented in this paper. SPDN is a classic combinatorial optimization problem having the status of a very difficult problem (-hard problem) and it is known as an optimization model for a broad class of problems in networks. Several exact and heuristic approaches have been designed for SPDN in the last twenty five years. Some papers analyze theoretical and experimental behavior of heuristics for SPDN, specially for undirected networks, but none of these has studied the worst-case performance of Wong''s heuristic. In this paper, we find a lower bound for that performance and show that this bound is consistent with comparable results in the literature on SPDN and its undirected version. [Copyright &y& Elsevier]

The Steiner ratio is the greatest lower bound of the ratios of the Steiner Minimal Tree- by the Minimum Spanning Tree-lengths running over all finite subsets of a metric space. We will discuss this quantity for finite-dimensional Banach spaces of high dimension. Particularly, let the quantity Cd defined as the upper bound of the Steiner ratio of all d-dimensional Banach spaces, thenlimlower limit d→∞ Cd=limlower limit d→∞ md(B(2)),where md(B(2)) denotes the Steiner ratio of the d-dimensional Euclidean space. [Copyright &y& Elsevier]

We study combinatorial and probabilistic properties of cover-free codes and block designs which are useful for their efficient application as the first stage of two-stage group testing procedures. Particular attention is paid to these procedures because of their importance in such applications as monoclonal antibody generation and cDNA library screening. [Copyright &y& Elsevier]

In anonymous secret sharing schemes, the secret can be reconstructed without knowledge of which participants hold which shares. In this paper, we derive a tighter lower bound on the size of the shares than the bound of Blundo and Stinson for anonymous (k,n)-threshold schemes with 1. Our bound is tight for k=2. We also show a close relationship between optimum anonymous (2,n)-threshold secret schemes and combinatorial designs. [Copyright &y& Elsevier]