共查询到20条相似文献,搜索用时 15 毫秒
1.
The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time. 相似文献
2.
In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset gi is called a group and the vertices in ?igi are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(maxi|gi|)·logm) provided by the LP based approaches. 相似文献
3.
A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|9) time, to solve the path cover problem on distance-hereditary graphs. 相似文献
4.
Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/2, where D is the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger’s conjecture. 相似文献
5.
Faisal N. Abu-Khzam Amer E. Mouawad Mathieu Liedloff 《Journal of Discrete Algorithms》2011,9(3):252-262
In the Connected Red–Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of G is adjacent to some vertex in S. The problem can be solved in O?(2n−|B|) time by reduction to the Weighted Steiner Tree problem. Combining exhaustive enumeration when |B| is small with the Weighted Steiner Tree approach when |B| is large, solves the problem in O?(n1.4143). In this paper we present a first non-trivial exact algorithm whose running time is in O?(n1.3645). We use our algorithm to solve the Connected Dominating Set problem in O?(n1.8619). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O?(n1.8966). 相似文献
6.
LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw
e
, edge capacitiesc
e
,e∈E, and node setT
1,…,T
N
, find edge setsS
1,…,S
N
such that eachS
k
is a Steiner tree forT
k
, at mostc
e
of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem
in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from
a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this
paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each
inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for
the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities
that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes
of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper
(in this issue). 相似文献
7.
In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph Ga,b can be defined as follows. The vertices of Ga,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999 相似文献
8.
Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by dG(S) or d(S). The Steiner n-eccentricity en(v) and Steiner n-distance dn(v) of a vertex v in G are defined as en(v)=max{d(S)| SV(G), |S|=n and vS} and dn(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center Cn(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median Mn(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that Cn(T) is contained in Cn+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that Mn(T) is contained in Mn+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which Cn(G)Cn+1(G). We also show that for each n2 there is a distance–hereditary graph G such that Mn(G)Mn+1(G). Despite these negative examples, we prove that if G is a block graph then Mn(G) is contained in Mn+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described. 相似文献
9.
Jóse Cáceres 《Discrete Mathematics》2009,309(19):5828-880
Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering. 相似文献
10.
The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method, we begin by proving the simpler related upper bounds (4(|V|−1)−|E|)/3 and 4|V|2/3|E| on the diameter (for connected planar graphs), which are also tight. 相似文献
11.
Jafar Fathali Hossein T. Kakhki Rainer E. Burkard 《Central European Journal of Operations Research》2006,14(3):229-246
Let a graph G = (V, E) with vertex set V and edge set E be given. The classical graph version of the p-median problem asks for a subset
of cardinality p, so that the (weighted) sum of the minimum distances from X to all other vertices in V is minimized. We consider the semi-obnoxious case, where every vertex has either a positive or a negative weight. This gives rise to two different objective functions, namely the weighted sum of the minimum distances from X to the vertices in V\X and, differently, the sum over the minimum weighted distances from X to V\X. In this paper an Ant Colony algorithm with a tabu restriction is designed for both problems. Computational results show its superiority with respect to a previously investigated variable neighborhood search and a tabu search heuristic.This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung. 相似文献
12.
The Node Weighted Steiner Tree Problem (NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on
the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints
and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results
refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this
formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation
on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still
valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm
solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances,
derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem.
Received: March 2005, Revised: September 2005
AMS classification:
68M10, 90C10, 90C57
This work has been partially supported by the Ministero dell'Istruzione, Universitá e Ricerca (MIUR), Italy 相似文献
13.
A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. 相似文献
14.
Let n, k, and t be integers satisfying . A Steiner system with parameters t, k, and n is a k‐uniform hypergraph on n vertices in which every set of t distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for . In this note we prove that for every and sufficiently large n, there exists an almost Steiner system with parameters t, k, and n; that is, there exists a k‐uniform hypergraph on n vertices such that every set of t distinct vertices is covered by either one or two edges. 相似文献
15.
A setE ofk edges in a multigraphG=(V,E) is said to be ak most vital edge set (k-MVE set) if these edges being removed fromG, the resultant graphG=(V,E –E) has minimum number of spanning trees. The problem of finding ak-MVE set for two-terminal series-parallel graphs is considered in this paper. We present anO (|E|) time algorithm for the casek=1, and anO(|V|
k
+|E|) time algorithm for arbitraryk. 相似文献
16.
In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold
, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of
of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|2 + |H|)-time, ΔE-approximation algorithm for this problem, where ΔE ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where ΔE = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|2), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function. 相似文献
17.
E. V. Pankratiev A. M. Chepovskiy E. A. Cherepanov S. V. Chernyshev 《Journal of Mathematical Sciences》2005,128(6):3487-3495
We consider a large-scale directed graph G = (V, E) whose edges are endowed with a family of characteristics. A subset of vertices of the graph, V′ ⊂ V, is selected and some additional conditions are imposed on these vertices. An algorithm for reducing the optimization problem on the graph G to an optimization problem on the graph G′ = (V′, E′) of a lower dimension is developed. The main steps of the solution and some methods for constructing an approximate solution to the problem on the transformed graph G′ are presented.__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 235–251, 2003. 相似文献
18.
A topological graph is a graph G=(V, E) on a topological space V such that the edge set E is a closed subset of the product space V x V. If the graph contains no infinite independent set then, by a well-known theorem of Erdös, Dushnik and Miller, for any infinite set LV, there is a subset LL of the same oardinality |L| = |L| such that the restriction G L is a complete graph. We investigate the question of whether the same conclusion holds if we weaken the hypothesis and assume only that some dense subset AV does not contain an infinite independent set. If the cofinality cf (|L|)>|A|, then there is an L as before, but if cf (|L|)<-|A|, then some additional hypothesis seems to be required. We prove that, if the graph GA is a comparability graph and A is a dense subset, then for any set LV such that cf (|L|)>, there is a subset LL of size |L|=|L| such that GL is complete. The condition cf (|L|)> is needed.Research supported by NSERC grant #A5198. 相似文献
19.
In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n2) in time O(n2lgn) and yields a query time of O((1+min(m,|V(q)|))lg2n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg1+m) for a small positive constant >0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min(|E|,mn))2) space and an additional O(m(min(|E|,mn))2) preprocessing time. 相似文献
20.
《Quaestiones Mathematicae》2013,36(2):159-164
AbstractThe Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence so(G),s1 (G),…,8p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized. 相似文献