Search

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits an "almost" Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (www.youtube.com/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs though under a relaxation of the original formulation. Second, we present a "parameteric version" of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of \(\mathcal {O}(k)\) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into \(\mathcal {O}(k)\) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly super-exponential) algorithms for well-studied problems such as Min Bisection, Steiner Cut, s-Way Cut, and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best-known algorithms for these problems on general graphs. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

After the departure of Kotzig and Rosa, the leadership of the seminar was assumed by Juraj Bosák, originally a student of Kotzig, later his long-time collaborator, and an active member of the seminar from its very beginnings. Kotzig and Bosák were among the first to present lectures at a graph theory conference (with Kotzig delivering the first talk in 1963, in Smolenice, Slovakia). Many young Slovak mathematicians benefited from these contacts, and had Kotizig and Rosa not left, the development of graph theory in Slovakia at the international level may have been delayed by many years. The Beginning of the Seminar (Early 1960s) The Bratislava graph theory seminar was established through the initiative of the Slovak mathematician Anton Kotzig, who prior to founding the seminar was (among his other activities) the rector of the University of Economics in Bratislava from 1952 to 1958. [Extracted from the article]

A rearrangement operation makes a small graph-theoretical change to a phylogenetic network to transform it into another one. For unrooted phylogenetic trees and networks, popular rearrangement operations are tree bisection and reconnection (TBR) and prune and regraft (PR) (called subtree prune and regraft (SPR) on trees). Each of these operations induces a metric on the sets of phylogenetic trees and networks. The TBR-distance between two unrooted phylogenetic trees T and T' can be characterised by a maximum agreement forest, that is, a forest with a minimum number of components that covers both T and T' in a certain way. This characterisation has facilitated the development of fixed-parameter tractable algorithms and approximation algorithms. Here, we introduce maximum agreement graphs as a generalisations of maximum agreement forests for phylogenetic networks. While the agreement distance - the metric induced by maximum agreement graphs - does not characterise the TBR-distance of two networks, we show that it still provides constant-factor bounds on the TBR-distance. We find similar results for PR in terms of maximum endpoint agreement graphs. [ABSTRACT FROM AUTHOR]

The flower at a point x in a Steiner triple system (X; B) is the set of all triples containing x. Denote by J3F(r) the set of all integers k such that there exists a collection of three STS(2r+1) mutually intersecting in the same set of k + r triples, r of them being the triples of a common flower. In this article we determine the set J3F(r) for any positive integer r = 0, 1 (mod 3) (only some cases are left undecided for r = 6, 7, 9, 24), and establish that J3F(r) = I3F(r) for r = 0, 1 (mod 3) where I3F(r) = {0, 1,. . ., 2r(r-1)/3-8, 2r(r-1)/3-6, 2r(r-1)/3}. [ABSTRACT FROM AUTHOR]

. [Extracted from the article]

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]

Abstract The Steiner distance of vertices in a set S is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets S of cardinality k is called the Steiner k -Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner k -Wiener index. The same extremal problems are also considered for trees with a given number of segments. [ABSTRACT FROM AUTHOR]

In this paper, we study the Steiner hyper-Wiener index of a graph, which is obtained from the standard hyper-Wiener index by replacing the classical graph distance with the Steiner distance. It is shown how this index is related to the Steiner Hosoya polynomial, which generalizes similar result for the standard hyper-Wiener index. Next, we show how the Steiner 3-hyper-Wiener index of a modular graph can be expressed by using the classical graph distances. As the main result, a method for computing this index for median graphs is developed. Our method makes computation of the Steiner 3-hyper-Wiener index much more efficient. Finally, the method is used to obtain the closed formulas for the Steiner 3-Wiener index and the Steiner 3-hyper-Wiener index of grid graphs. [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]

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]

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∊V (G) dG(u, v), where dG(u,v) is the distance (the length a shortest path) between the vertices u and v in G. For S ∢V (G), the Steiner distance d(S) of the vertices of S, introduced by Chartrand et al. in 1989, is the minimum size of a connected subgraph of G whose vertex set contains S. The k-th Steiner Wiener index SWk(G) of G is defined as SWk(G) = ∑S∢V (G)∣S∣=k d(S). We investigate the following problem: Fixed a positive integer k, for what kind of positive integer w does there exist a connected graph G (or a tree T) of order n ≥ k such that SWk(G) = w (or SWk(T) = w)? In this paper, we give some solutions to this problem. [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 unique Steiner triple system of order 7 has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in C d to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d = 10 is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in 10 real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound. [ABSTRACT FROM AUTHOR]

In this article, we consider the Node-Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node-induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node-cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition-based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well-known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 33-51 2017 [ABSTRACT FROM AUTHOR]

We obtain the number of different Steiner triple systems S ( 2 m − 1 , 3 , 2 ) of rank 2 m − m + 2 over the field F 2 . [ABSTRACT FROM AUTHOR]

We propose a new approach to studies on partial Steiner triple systems consisting in determining complete graphs contained in them. We establish the structure which complete graphs yield in a minimal PSTS that contains them. As a by-product we introduce the notion of a binomial PSTS as a configuration with parameters of a minimal PSTS with a complete subgraph. A representation of binomial PSTS with at least a given number of its maximal complete subgraphs is given in terms of systems of perspectives. Finally, we prove that for each admissible integer there is a binomial PSTS with this number of maximal complete subgraphs. [ABSTRACT FROM AUTHOR]

We consider the Steiner Multicut problem, which asks, given an undirected graph G , a collection T = { T 1 , … , T t } , T i ⊆ V ( G ) , of terminal sets of size at most p , and an integer k , whether there is a set S of at most k edges or nodes such that of each set T i at least one pair of terminals is in different connected components of G − S . We provide a dichotomy of the parameterized complexity of Steiner Multicut . For any combination of k , t , p , and the treewidth tw ( G ) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W [ 1 ] -hard, or (para-) NP -complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP -hardness dichotomy (by restricting k , t , p , tw ( G ) to constant or unbounded). [ABSTRACT FROM AUTHOR]

A complete weighted graph, $$G(X,\varGamma ,W)$$ , is considered. Let $$\tilde{X}\subset X$$ be some subset of vertices and, by definition, a Steiner tree is any tree in the graph G such that the set of the tree vertices includes set $$\tilde{X}$$ . The Steiner tree problem consists of constructing the minimum-length Steiner tree in graph G, for a given subset of vertices $$\tilde{X}$$ The effectively computable estimate of the minimal Steiner tree is obtained in terms of the mean value and the variance over the set of all Steiner trees. It is shown that in the space of the lengths of the graph edges, there exist some regions where the obtained estimate is better than the minimal spanning tree-based one. [ABSTRACT FROM AUTHOR]

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

The problem we consider in this article ismotivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well-balanced design--that is, a family of blocks--each of size k, such that each j-element subset of V, 1 ≤ j ≤ k, belongs to the same or almost the same number of blocks (difference at most one). The existence of well-balanced designs is a difficult problem as it contains, as a subproblem, the existence of Steiner systems. We completely solve the case k = 2 and give bounds and constructions for k = 3 and some values of v and b. [ABSTRACT FROM AUTHOR]

The class of ( ( n + 1 2 ) n − 1 ( n + 1 3 ) 3 ) -configurations which contain at least n − 2 K n -graphs coincides with the class of so called systems of triangle perspectives i.e. of configurations which contain a bundle of n − 2 Pasch configurations with a common line. For n = 5 the class consists of all binomial partial Steiner triple systems on 15 points, that contain at least three K 5 -graphs. In this case a complete classification of respective configurations is given and their automorphisms are determined. [ABSTRACT FROM AUTHOR]

We consider complete multigraphs $${K_n^m}$$ on n vertices with every pair joined by m edges. We embed these graphs to triangulate $${S_n^k}$$ , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2 m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m = 1, k = 1 of simple graphs in surfaces without pinch points. [ABSTRACT FROM AUTHOR]

Let P be a point set on the plane, and consider whether P is quadrangulatable, that is, whether there exists a 2-connected plane graph G with each edge a straight segment such that V( G) = P, that the outer cycle of G coincides with the convex hull Conv( P) of P, and that each finite face of G is quadrilateral. It is easy to see that it is possible if and only if an even number of points of P lie on Conv( P). Hence we give a k-coloring to P, and consider the same problem, avoiding edges joining two vertices of P with the same color. In this case, we always assume that the number of points of P lying on Conv( P) is even and that any two consecutive points on Conv( P) have distinct colors. However, for every k ≥ 2, there is a k-colored non-quadrangulatable point set P. So we introduce Steiner points, which can be put in any position of the interior of Conv( P) and each of which may be colored by any of the k colors. When k = 2, Alvarez et al. proved that if a point set P on the plane consists of $${\frac{n}{2}}$$ red and $${\frac{n}{2}}$$ blue points in general position, then adding Steiner points Q with $${|Q| \leq \lfloor \frac{n-2}{6} \rfloor + \lfloor \frac{n}{4} \rfloor +1}$$ , P ∪ Q is quadrangulatable, but there exists a non-quadrangulatable 3-colored point set for which no matter how many Steiner points are added. In this paper, we define the winding number for a 3-colored point set P, and prove that a 3-colored point set P in general position with a finite set Q of Steiner points added is quadrangulatable if and only if the winding number of P is zero. When P ∪ Q is quadrangulatable, we prove $${|Q| \leq \frac{7n+34m-48}{18}}$$ , where | P| = n and the number of points of P in Conv( P) is 2 m. [ABSTRACT FROM AUTHOR]

Let G = ( V, E) be a simple graph and let T = ( P, B) be a Steiner triple system. Let φ be a one-to-one function from V to P. Any edge e = { u, v} has its image { φ( u), φ( v)} in a unique block in B. We also denote this induced function from edges to blocks by φ. We say that T represents G if there exists a one-to-one function φ : V → P such that the induced function φ : E → B is also one-to-one; that is, if we can represent vertices of the graph by points of the triple system such that no two edges are represented by the same block. In this paper we examine when a graph can be represented by an STS. First, we find a bound which ensures that every graph of order n is represented in some STS of order f( n). Second, we find a bound which ensures that every graph of order n is represented in every STS of order g( n). Both of these answers are related to finding an independent set in an STS. Our question is a generalization of finding such independent sets. We next examine which graphs can be represented in STS's of small orders. Finally, we give bounds on the orders of STS's that are guaranteed to embed all graphs of a given maximum degree. [ABSTRACT FROM AUTHOR]

The roll-out of new infrastructural networks in space-constrained areas requires the careful consideration of limited paths. This design task is aggravated if the number and/or location of connectors is unknown. The novel combination of graph theory and concepts of exploratory modelling in this contribution allow for an analysis of most likely paths that maximise the value for the planners. We apply this approach to two proposed energy networks in the Netherlands: a biogas network of farmers in the province of Overijssel and an LNG pipeline connecting industries in the Port of Rotterdam. The examples demonstrate the ease of use and simplicity of this approach that transparently deals with unknowns. [ABSTRACT FROM AUTHOR]

An [ABSTRACT FROM AUTHOR]

A k-bar visibility representation of a digraph G assigns each vertex at most k horizontal segments in the plane so that G has an arc uv if and only if some segment for u "sees" some segment for v above it by a vertical line of sight. The (bar) visibility number b(G) of a digraph G is the least k permitting such a representation. Among other results, we show that b(G) ≤ 4 when G is a planar digraph (reducing to 3 when the underlying graph has no triangles), b(G) ≤ 2 when G is outerplanar, and b(G) ≤ (n + 10)/3 when G has n vertices. When G is the n-vertex transitive tournament, b(G) ≤ 7n/24 + 2√ n log n, improving to b(G) < 3n/14 + 42 when n is sufficiently large. Our tools include arboricity, interval number, and Steiner systems. [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]

Given a set of customers, a set of potential facility locations, and some interconnection nodes, the goal of the connected facility location problem (ConFL) is to find the minimum-cost way of assigning each customer to exactly one open facility and connecting the open facilities via a Steiner tree. The sum of costs needed for building the Steiner tree, facility opening costs, and the assignment costs needs to be minimized. If the number of edges between a prespecified node (the so-called root) and each open facility is limited, we speak of the hop constrained facility location problem (HC ConFL). This problem is of importance in the design of data-management and telecommunication networks. In this article we provide the first theoretical and computational study for this new problem that has not been studied in the literature so far. We propose two disaggregation techniques that enable the modeling of HC ConFL: (i) as a directed (asymmetric) ConFL on layered graphs, or (ii) as the Steiner arborescence problem (SA) on layered graphs. This allows for usage of best-known mixed integer programming models for ConFL or SA to solve the corresponding hop constrained problem to optimality. In our polyhedral study, we compare the obtained models with respect to the quality of their linear programming lower bounds. These models are finally computationally compared in an extensive computational study on a set of publicly available benchmark instances. Optimal values are reported for instances with up to 1,300 nodes and 115,000 edges. [ABSTRACT FROM AUTHOR]

A 3-graph is said to contain a generalized 4-cycle if it contains 4 edges A, B, C, D such that A ∩ B=C ∩ D =∅ and A ∪ B=C ∪ D. We show that a 3-graph in which every pair of vertices is contained in at least 4 edges must contain a generalized 4-cycle. When the number of vertices, n, is equivalent to 1 or 5 modulo 20, this result is optimum, in the sense that for such n there are 3-graphs where every pair of vertices is contained in 3 edges but which do not contain a generalized 4-cycle. [ABSTRACT FROM AUTHOR]

Abstract: A Steiner quadruple system is said to be -resolvable if its blocks can be partitioned into parts such that each point of occurs in exactly two blocks in each part. The necessary condition for the existence of -resolvable Steiner quadruple systems s is or 10 (mod 12). Hartman and Phelps in [A. Hartman, K.T. Phelps, Steiner quadruple systems, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992, pp. 205–240] posed a question whether the necessary condition for the existence of -resolvable Steiner quadruple systems is sufficient. In this paper, we consider the last twenty orders of -resolvable Steiner quadruple systems and show that the necessary condition for the existence of -resolvable Steiner quadruple systems is also sufficient except for the order 10. [Copyright &y& Elsevier]

Abstract: The block graph of a Steiner triple system of order v is a strongly regular graph. For large v, every strongly regular graph with these parameters is the block graph of a Steiner triple system, but exceptions exist for small orders. An explanation for some of the exceptional graphs is here provided via the concept of switching. (Group divisible designs corresponding to) Latin squares are also treated in an analogous way. Many new strongly regular graphs are obtained by switching and by constructing graphs with prescribed automorphisms. In particular, new strongly regular graphs with the following parameters that do not come from Steiner triple systems or Latin squares are found: , , , , , and . [Copyright &y& Elsevier]

Abstract: We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in time, where tw is the graphʼs treewidth and the Bell number is the number of partitions of a k-element set. This is a linear-time algorithm for graphs with fixed treewidth and a polynomial algorithm for . While being faster than the previously known algorithms, the coloring scheme used in our algorithm can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems with similar runtime bounds. [Copyright &y& Elsevier]

Abstract: Under the design experience of a single open on any wiring segment in a signal net, it is known that the non-tree topology for a signal net does not need any adjacent loop. In this paper, based on two time-equivalent splitting operations in a cyclic connection, an accurate transformation-based analysis approach is firstly proposed to compute the timing delays of all the sinks in a non-tree topology without any adjacent loop. Furthermore, given a resource constraint, a 0–1 integer linear programming (ILP) formulation for resource-constrained link insertion is proposed to insert timing-driven geometrical links to reduce the delay of the critical path in a given rectilinear Steiner tree according to the definition of timing-driven redundant links and the design experience of a single open on any wiring segment. For tested Steiner trees, the experimental results show that the 0–1 ILP formulation based on our proposed transformation-based timing analysis has 21.0% and 23.5% of the delay reduction of the critical path under the resource constraints for 10% and 20% of the total wirelength of the original tree in reasonable CPU time on the average, respectively. [Copyright &y& Elsevier]

We present efficient algorithms that implement four local searches for the Steiner problem in graphs: vertex insertion, vertex elimination, key-path exchange, and key-vertex elimination. In each case, we show how to find an improving solution (or prove that none exists in the neighborhood) in O(m log n) time on graphs with n vertices and m edges. Many of the techniques and data structures we use are relevant in the study of dynamic graphs in general, beyond Steiner trees. Besides the theoretical interest, our results have practical impact: These local searches have been shown to find good-quality solutions in practice, but high running times limited their applicability. [ABSTRACT FROM AUTHOR]

Abstract: A friendship 3-hypergraph is a 3-hypergraph in which for any 3 distinct vertices , and , there exists a unique fourth vertex such that , , are 3-hyperedges. Sós constructed friendship 3-hypergraphs using Steiner triple systems. Hartke and Vandenbussche showed that any friendship 3-hypergraph can be partitioned into ’s. (A is the set of four hyperedges of size three that can be formed from a set of 4 elements.) These ’s form a set of 4-tuples which we call a friendship design. We define a geometric friendship design to be a resolvable friendship design that can be embedded into an affine geometry. Refining the problem from friendship designs to geometric friendship designs allows us to state some structure results about these geometric friendship designs and decrease the search space when searching for geometric friendship designs. Hartke and Vandenbussche discovered 5 new examples of friendship designs which happen to be geometric friendship designs. We show the 3 non-isomorphic geometric designs on 16 vertices are the only such non-isomorphic geometric designs on 16 vertices. We also improve the known lower and upper bounds on the number of hyperedges in any friendship 3-hypergraph. Finally, we show that no friendship 3-hypergraph exists on 11 or 12 points. [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: We prove that, aside from the complete multipartite graphs and graphs of Steiner type, there are only finitely many connected strongly regular graphs with a regular star complement of prescribed degree . We investigate the possible parameters when . [Copyright &y& Elsevier]

The concepts of edge Steiner set and edge Steiner number of a graph are investigated in this study. A necessary and sufficient condition for a graph G to satisfy ste(G) = |V (G)|-1, where ste(G) denotes the edge Steiner number of G, is obtained. Edge Steiner sets in the joins of graphs are also studied and the Steiner numbers of these graphs are determined. [ABSTRACT FROM AUTHOR]

Higman asked which block graphs of Steiner triple systems of order v satisfy the 4-vertex condition and left the cases v = 9, 13, 25 unsettled.We give a complete answer to this question by showing that the affine plane of order 3 and the binary projective spaces are the only such systems. The major part of the proof is to show that no block graph of a Steiner triple system of order 25 satisfies the 4-vertex condition. [ABSTRACT FROM AUTHOR]

Abstract: Given a multipartite graph G the generalized minimum spanning tree problem is to find a tree of minimal cost that includes a vertex from each part. This paper proposes several versions of the GRASP metaheuristic for the problem. The GRASP approach is based on constructive heuristics as well as on additional improvement mechanisms such as path-relinking and iterated local search. Several computational experiments are performed over a set of existing instances. A cut generation algorithm is proposed that is able to find lower bounds, based on a formulation for Steiner’s problem in directed graphs. The computational results show that the best versions of the GRASP approach use improvement mechanisms. The solutions found are better than most of the known solutions in the literature and require significantly less computer time. Furthermore, a set of rules is defined for pre-processing the instances, based on the Bottleneck distance concept. Using those rules, it was possible to reduce the size of the instances to an average of 14% of the number of edges in relation to the original graphs. [Copyright &y& Elsevier]

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log nlog k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ ε. [ABSTRACT FROM AUTHOR]

Abstract: We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph with edge costs, a collection of ordered node pairs, and an integer , find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs . When , we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. (1999) , and for DSF by Chekuri et al. (2008) . Our main result is achieving the first sub-linear in terms of approximation ratio for DSF. Specifically, we give an -approximation scheme for DSF. For k-DSF we give a simple greedy -approximation algorithm. This improves upon the best known ratio by Charikar et al. (1999) , and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 ). This algorithm uses a new structure called start-junction tree which may be of independent interest. [Copyright &y& Elsevier]

Abstract: Hybrid approaches are often recommended for dealing in an efficient manner with complex problems that require considerable computational time. In this study, we follow a similar approach consisting of combining spectral clustering and ant colony optimization in a two-stage algorithm for the purpose of efficiently solving the Steiner tree problem in large graphs. The idea of the two-stage approach, called ESC–IAC, is to apply a divide-and-conquer strategy which consists of breaking down the problem into sub-problems to find local solutions before combining them. In the first stage, graph segments (clusters) are generated using an ensemble spectral clustering method for enhancing the quality; whereas in the second step, parallel independent ant colonies are implemented to find local and global minima of the Steiner tree. To illustrate the efficiency and accuracy, ESC–IAC is applied in the context of a geographical application relying on real-world as well as artificial benchmarks. [Copyright &y& Elsevier]