Results 111 to 120 of about 4,149 (163)
Some of the next articles are maybe not open access.
Finding Minimum Spanning Trees
SIAM Journal on Computing, 1976This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with $O(m\log \log n)$ worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense graphs (those for which m is $\Omega (n^{1 + \varepsilon } )$ for ...
Cheriton, David, Tarjan, Robert Endre
openaire +2 more sources
2019
The atoll of Taka-Tuka-Land in the South Seas asks you for help. The people want to connect their islands by ferry lines. Since money is scarce, the total cost of the connections is to be minimized. It needs to be possible to travel between any two islands; direct connections are not necessary. You are given a list of possible connections together with
Peter Sanders +3 more
openaire +1 more source
The atoll of Taka-Tuka-Land in the South Seas asks you for help. The people want to connect their islands by ferry lines. Since money is scarce, the total cost of the connections is to be minimized. It needs to be possible to travel between any two islands; direct connections are not necessary. You are given a list of possible connections together with
Peter Sanders +3 more
openaire +1 more source
The Capacitated Minimum Spanning Tree
Networks, 1973AbstractThe capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorithm to obtain optimal solutions.
Chandy, K. M., Lo, Tachen
openaire +1 more source
On generalized minimum spanning trees
European Journal of Operational Research, 2001zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Feremans, Corinne +2 more
openaire +3 more sources
2010
In this chapter, we study the behavior of stochastic search algorithms on an important graph problem. We consider the well-known problem of computing a minimum spanning tree in a given undirected connected graph with n vertices and m edges. The problem has many applications in the area of network design.
Frank Neumann, Carsten Witt
openaire +1 more source
In this chapter, we study the behavior of stochastic search algorithms on an important graph problem. We consider the well-known problem of computing a minimum spanning tree in a given undirected connected graph with n vertices and m edges. The problem has many applications in the area of network design.
Frank Neumann, Carsten Witt
openaire +1 more source
Finding Minimum Congestion Spanning Trees
ACM Journal of Experimental Algorithmics, 1999Given a weighted graph <i>G = (V, E)</i>, a positive integer <i>k</i>, and a penalty function <i>w<inf>p</inf></i>, we want to find <i>k</i> spanning trees on <i>G</i>, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty ...
Renato Werneck +2 more
openaire +1 more source
Counting Minimum Weight Spanning Trees
Journal of Algorithms, 1997Summary: We present an algorithm for counting the number of minimum weight spanning trees, based on the fact that the generating function for the number of spanning trees of a given graph, by weight, can be expressed as a simple determinant.
Broder, Andrei Z., Mayr, Ernst W.
openaire +2 more sources
Approximating k-hop minimum-spanning trees
Operations Research Letters, 2005Given a complete graph on~$n$ nodes with metric edge costs, the minimum-cost k-hop spanning tree ($k$HMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most $k$ edges. We present an algorithm that computes such a tree of total expected cost $O(log n)$ times that of a minimum-cost $k$-hop
Althaus, Ernst +5 more
openaire +2 more sources
2004
Suppose you have a business with several branch offices and you want to lease phone lines to connect them with each other. Your goal is to connect all your offices with the minimum total cost. The resulting connection should be a spanning tree since if it is not a tree, you can always remove some edges without losing the connectivity to save money.
openaire +2 more sources
Suppose you have a business with several branch offices and you want to lease phone lines to connect them with each other. Your goal is to connect all your offices with the minimum total cost. The resulting connection should be a spanning tree since if it is not a tree, you can always remove some edges without losing the connectivity to save money.
openaire +2 more sources
2013
A minimum spanning tree of a weighted graph is its spanning tree T with a minimum total cost of edges in T of all possible spanning trees. Minimum spanning trees have many applications in computer networks. In this chapter, we investigate synchronous and asynchronous distributed algorithms to construct minimum spanning trees.
openaire +1 more source
A minimum spanning tree of a weighted graph is its spanning tree T with a minimum total cost of edges in T of all possible spanning trees. Minimum spanning trees have many applications in computer networks. In this chapter, we investigate synchronous and asynchronous distributed algorithms to construct minimum spanning trees.
openaire +1 more source