共查询到20条相似文献,搜索用时 15 毫秒
1.
We extend and strengthen the result that, in the complete graphK
n with independent random edge-lengths uniformly distributed on [0, 1], the expected length of the minimum spanning tree tends to(3) asn. In particular, ifK
n is replaced by the complete bipartite graphK
n, n then there is a corresponding limit of 2 (3). 相似文献
2.
Given n points in the Euclidean plane, the degree-δ minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most δ. The problem is NP-hard for 2≤δ≤3, while the NP-hardness of the problem is open for δ=4. The problem is polynomial-time solvable when δ=5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most times the weight of an MST. 相似文献
3.
Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We
prove that, under theL
p
norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an
even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree
for arbitraryL
p
metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite
set of points in the rectilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear
space the maximum possible degree of a minimum-degree MST is either 13 or 14.
Gabriel Robins was partially supported by NSF Young Investigator Award MIP-9457412. Jeffrey Salowe was partially supported
by NSF Grants MIP-9107717 and CCR-9224789. 相似文献
4.
5.
《European Journal of Operational Research》2001,134(2):457-458
The generalized minimum spanning tree problem consists of designing a minimum cost tree spanning several clusters. The purpose of this note is to pinpoint several inaccuracies contained in a previous publication and to propose a valid formulation for this problem. 相似文献
6.
7.
Alexandr V. Kostochka 《Random Structures and Algorithms》1990,1(3):277-285
A question about the evolution of random spanning subgraphs G p of bipartite regular so called cubelike graphs G is considered. It is shown that for G p of any large enough cubelike graph G the threshold to have a 1-factor is the same as the threshold to have no isolated vertices. This generalizes a conjecture of K. Weber. 相似文献
8.
Degree conditions on the vertices of a t‐tough graph G (1 ≤ t < 3) are presented which ensure the existence of a spanning cubic subgraph in G. These conditions are best possible to within a small additive constant for every fixed rational t ∈[1,4/3)∪[2,8/3). © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 119–141, 2004 相似文献
9.
We study some combinatorial and algorithmic problems associated with an arbitrary motion of input points in space. The motivation for such an investigation comes from two different sources:computer modeling andsensitivity analysis. In modeling, the dynamics enters the picture since geometric objects often model physical entities whose positions can change over time. In sensitivity analysis, the motion of the input points might represent uncertainties in the precise location of objects. The main results of the paper deal with state transitions in the minimum spanning tree when one or more of the input points move arbitrarily in space. In particular, questions of the following form are addressed: (i) How many different minimum spanning trees can arise if one point moves while the others remain fixed? (ii) When does the minimum spanning tree change its topology if all points are allowed to move arbitrarily? 相似文献
10.
In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/13 + 1/23 + 1/33 +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log2 logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log2 logn, then the weight is doubly-exponentially large in log2 logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log2 logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log2 logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log2 logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log2 logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ . 相似文献
11.
Classification of interpolation theorems for spanning trees and other families of spanning subgraphs
We say that a graphical invariant i of a graph interpolates over a family F of graphs if i satisfies the following property: If m and M are the minimum and maximum values (respectively) of i over all graphs in F then for each k, m ? k ? M, there is a graph H in F for which i(H)= k. In previous works it was shown that when F is the set of spanning trees of a connected graph G, a large number of invariants interpolate (some of these invariants require the additional assumption that G be 2-connected). Although the proofs of all these results use the same basic idea of gradually transforming one tree into another via a sequence of edge exchanges, some of these processes require sequences that use more properties of trees than do others. We show that the edge exchange proofs can be divided into three types, in accordance with the extent to which the exchange sequence depends upon properties of spanning trees. This idea is then used to obtain new interpolation results for some invariants, and to show how the exchange methods and interpolation results on spanning trees can be extended to other families of spanning subgraphs. 相似文献
12.
On Steiner trees and minimum spanning trees in hypergraphs 总被引:3,自引:0,他引:3
The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach. 相似文献
13.
14.
Pu Gao 《Random Structures and Algorithms》2013,43(3):338-353
In this paper, we examine the moments of the number of d ‐factors in \begin{align*}\mathcal{ G}(n,p)\end{align*} for all p and d satisfying d3 = o(p2n). We also determine the limiting distribution of the number of d ‐factors inside this range with further restriction that \begin{align*}(1-p)\sqrt{dn}\to\infty\end{align*} as n →∞.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
15.
The construction of minimum spanning trees (MSTs) of weighted graphs is a problem that arises in many applications. In this paper we will study a new parallel algorithm that constructs an MST of an N-node graph in time proportional to N lg N, on an computing system. The primary theoretical contribution of this paper is the new algorithm, which is an improvement over Sollin's parallel MST algorithm in several ways. On a more practical level, this algorithm is appropriate for implementation in VLSI technology. 相似文献
16.
Maximizing the minimum voter satisfaction on spanning trees 总被引:1,自引:0,他引:1
This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, can be determined efficiently given the goal of maximin voter satisfaction. In particular, we show that computing spanning trees for maximin voter satisfaction under voting rules such as approval voting or the Borda count is -complete for a variable number of voters whereas it remains polynomially solvable for a constant number of voters. 相似文献
17.
We show that almost everyG
m-out containsm edge disjoint spanning trees. 相似文献
18.
Pankaj K. Agarwal Herbert Edelsbrunner Otfried Schwarzkopf Emo Welzl 《Discrete and Computational Geometry》1991,6(1):407-422
We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE
d
in timeO(F
d
(N,N) log
d
N), whereF
d
(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE
d
. IfF
d
(N,N)=Ω(N
1+ε), for some fixed ɛ>0, then the running time improves toO(F
d
(N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)2/3+m log2
n+n log2
m) inE
3, which yields anO(N
4/3 log4/3
N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE
3. Ind≥4 dimensions we obtain expected timeO((nm)1−1/([d/2]+1)+ε+m logn+n logm) for the bichromatic closest pair problem andO(N
2−2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive ɛ.
The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer
Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's
work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the
Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”.
The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No.
3075 (project ALCOM). 相似文献
19.
The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()−1 Σ{x,y}⊂V(G) dG(x, y), where V(G) denotes the vertex set of G and dG(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K3‐free graphs, C4‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000 相似文献
20.