Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Finding minimum-cost flows by double scaling

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.     

Storing line segments in partition trees

We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n ), where=log₂(1+5)–10.695. The techniques are fairly simple and easy to understand.Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Dynamic partition trees

In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log² n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n ^· k ) where=log₂((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM).     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Euclidean minimum spanning trees and bichromatic closest pairs

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 log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. 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).     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Two improved algorithms for envelope and wavefront reduction

Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficientO(nlogn+m) time implementation of the Sloan algorithm, wheren is the number of rows (vertices), andm is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler RCM algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning. This work was partially supported by the U. S. National Science Foundation grants CCR-9412698, DMS-9505110, and ECS-9527169, by U. S. Department of Energy grant DE-FG05-94ER25216, and by the National Aeronautics and Space Administration under NASA Contract NAS1-19480 while the second author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA.     

2-noncrossing trees and 5-ary trees

Recently, Gu et al. [N.S.S. Gu, N.Y. Li, T. Mansour, 2-Binary trees: Bijections and related issues, Discrete Math. 308 (2008) 1209-1221] introduced 2-binary trees and 2-plane trees which are closely related to ternary trees. In this note, we study the 2-noncrossing tree, a noncrossing tree in which each vertex is colored black or white and there is no ascent (u,v) such that both the vertices u and v are colored black. By using the representation of Panholzer and Prodinger for noncrossing trees, we find a correspondence between the set of 2-noncrossing trees of n edges with a black root and the set of 5-ary trees with n internal vertices.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Connectivity threshold for random chordal graphs

We introduce a model for random chordal graphs. We determine the thresholds for: the first edge, completeness, isolated vertices and connectivity. Like the Erdös-Rényi model, the thresholds for isolated vertices and connectivity are the same. Unlike the Erdös-Rényi model in which the threshold occurs at 1/2n logn edges, this threshold occurs atO(n ²) edges.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Isomorphic factorizations of trees

A tree is even if its edges can be colored in two colors so that the monochromatic subgraphs are isomorphic. All even trees of maximum degree 3 in which no two vertices of degrees 1 or 3 are adjacent are determined. It is also shown that, for every n, there are only finitely many trees of maximum degree 3 and with n vertices of degree 3 that are not even. © 1995 John Wiley & Sons, Inc.     

Bipartite labelings of trees and the gracesize

Let T = (V, E) be a tree whose vertices are properly 2-colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ?, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α-size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) - f(v)|, uv ? E, taken over all bipartite labelings f of T. We investigate the asymptotic behavior of the α-size of trees. Let α(n) be the smallest α-size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5n/7. © 1995 John Wiley & Sons, Inc.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.     

ON NUMBER OF LEAVES ANDBANDWIDTH OF TREES

1.IntroductionFOragraphG=(V,E)oforderp,aonetoonemappingfromVinto{l,2,',p}iscalledanumberingofG.Definition1.1.SupposefisanumberingofG.LetBj(G)=(u57teif(u)--f(v)l.ThebandwidthofG,denotedbyB(G),isdefinedbyB(G)=min{Bf(G)IfisanumberingofG}.Thebandwidthproblemofgraphshasbecomeveryimportantsincethemid-sixties(see[21or[4]).Itisverydifficulttodeterminethebandwidthofagraph.GareyetallllshowedthatthebandwidthproblemisNP-completeevenifitisrestrictedtotreeswithmaximumdegree3.Soitisinterestingtoe…     

Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.