共查询到20条相似文献,搜索用时 15 毫秒
1.
David J. Aldous 《Random Structures and Algorithms》2001,18(4):381-418
The random assignment (or bipartite matching) problem asks about An=minπ ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EAn→ζ(2)=π2/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001 相似文献
2.
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). 相似文献
3.
J. Zafarani 《Mathematische Nachrichten》1995,174(1):317-322
In this paper we study the Grothendieck spaces among the operator spaces Le(E'c, F). Conditions under which Le(E'c, F) contains complemented copy of c0 are given. We apply these results to spaces of the type Cb(X; F) endowed with strict topologies. 相似文献
4.
Boris Pittel 《Random Structures and Algorithms》1990,1(3):311-342
For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define tn(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[tn(k) - nh(k)]n?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = kk?2ck?1e?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)?2θ(1 ? θ) for the second model. Here Te?T = ce?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc?1(β + β2/2) and variance n[c?1(β + β2/2) ?c?2(c + 1)β2], where βeβ = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core. 相似文献
5.
Behrooz Mashayekhy 《Indagationes Mathematicae》1997,8(4):529
In 1972 K.I. Tahara [7,2, Theorem 2.2.5], using cohomological methods, showed that if a finite group is the semidirect product of a normal subgroup N and a subgroup T, then M(T) is a direct factor of M(G), where M(G) is the Schur-multiplicator of G and in the finite case, is the second cohomology group of G. In 1977 W. Haebich [1, Theorem 1.7] gave another proof using a different method for an arbitrary group G.In this paper we generalize the above theorem. We will show that scNcM(T) is a direct factor of cM(G), where c[3, p. 102] is the variety of nilpotent groups of class at most c ≥ 1 and cM(G) is the Baer-invariant of the group G with respect to the variety c [3, p. 107]. 相似文献
6.
In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max e t(e)}/{Min e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max c L(c)}/{Min c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e. 相似文献
7.
The adaptable choosability number of a multigraph G, denoted cha(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that cha grows with ch, i.e. there is a function f tending to infinity such that cha(G)≥f(ch(G)). 相似文献
8.
Let c be a constant and (e1,f1),(e2,f2),…,(ecn,fcn) be a sequence of ordered pairs of edges from the complete graph Kn chosen uniformly and independently at random. We prove that there exists a constant c2 such that if c > c2, then whp every graph which contains at least one edge from each ordered pair (ei,fi) has a component of size Ω(n), and, if c < c2, then whp there is a graph containing at least one edge from each pair that has no component with more than O(n1?? vertices, where ? is a constant that depends on c2 ? c. The constant c2 is roughly 0.97677. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 相似文献
9.
Boris Pittel 《Random Structures and Algorithms》1994,5(2):337-347
A process of growing a random recursive tree Tn is studied. The sequence {Tn} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of Tn is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)?1, where γe1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc. 相似文献
10.
11.
H. Karami S. M. Sheikholeslami Abdollah Khodkar 《Czechoslovak Mathematical Journal》2008,58(3):595-603
The open neighborhood N
G
(e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ
st
′(G). Obviously, γ
st
′(G) is defined only for graphs G which have no connected components isomorphic to K
2. In this paper we present some lower bounds for γ
st
′(G). In particular, we prove that γ
st
′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ
st
′(T).
Research supported by a Faculty Research Grant, University of West Georgia. 相似文献
12.
A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ
e∋u
w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.
相似文献
13.
For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007 相似文献
14.
IfG andH are graphs, let us writeG→(H)2 ifG contains a monochromatic copy ofH in any 2-colouring of the edges ofG. Thesize-Ramsey number
r
e(H) of a graphH is the smallest possible number of edges a graphG may have ifG→(H)2. SupposeT is a tree of order |T|≥2, and lett
0,t
1 be the cardinalities of the vertex classes ofT as a bipartite graph, and let Δ(T) be the maximal degree ofT. Moreover, let Δ0, Δ1 be the maxima of the degrees of the vertices in the respective vertex classes, and letβ(T)=T
0Δ0+t
1Δ1. Beck [7] proved thatβ(T)/4≤r
e(T)=O{β(T)(log|T|)12}, improving on a previous result of his [6] stating thatr
e(T)≤Δ(T)|T|(log|T|)12. In [6], Beck conjectures thatr
e(T)=O{Δ(T)|T|}, and in [7] he puts forward the stronger conjecture thatr
e(T)=O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing thatr
e(T)=O{β(T)logΔ(T)}. 相似文献
15.
Edoardo Ballico 《Mathematische Nachrichten》1989,141(1):267-273
Nuclear convergence spaces are studied. It is shown that an Le-embedded convergence vector space E is LeLM-embedded if it is Schwartz and satisfies a certain countability condition which expresses that the set of filters converging to zero is essentially countable. Further it is shown that if E is LeLM-embedded and nuclear, then the identity E → E can be approximated with finite operators in the equable continuous convergence structure on L(E, E). This result is used in the study of the spectrum HomcHe(U) of the convergence algebra He(U) of holomorphic functions on a circled convex open set to prove sufficient conditions for the validity of the formula HomcHe(U) ~ U. 相似文献
16.
R. Kaufman 《Israel Journal of Mathematics》1985,50(4):353-356
Theorem. Let S be a bounded Suslin set in the plane. Then there is a bounded linear operator T in co, whose point spectrum σ
e
(T)=S. 相似文献
17.
A link between Ramsey numbers for stars and matchings and the Erd
s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K1,m in K2m−1 with edges e1, e2,…, em such that c(e1)+c(e2)++c(em)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(Kr(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z1, Z2,…, Zm of S such that c(Z1)+c(Z2)++c(Zm)≡0 (mod m). 相似文献
18.
19.
Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X1, X2, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max1 ≤ j ≤ n(Xj − jc)) − supt Tn E(Xt − tc) ≤ 1/e, where Tn is the collection of all stopping times t which are less than or equal to n almost surely. 相似文献
20.
In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} £ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} . 相似文献