Keyword: minimum spanning trees

Found 37 papers in total
Maximizing spanning trees in almost complete graphs
Maximizing spanning trees in almost complete graphs
1997,
We examine the family of graphs whose complements are a union of paths and cycles and...
Computing Prüfer codes efficiently in parallel
Computing Prüfer codes efficiently in parallel
2000,
A Prüfer code of a labeled free tree with n nodes is a sequence of length n...
An algorithm for enumerating all spanning trees of a directed graph
An algorithm for enumerating all spanning trees of a directed graph
2000,
We present an O(NV + V³) time algorithm for enumerating all spanning trees...
Near-optimal bounded-degree spanning trees
Near-optimal bounded-degree spanning trees
2001,
Random costs C ( i,j ) are assigned to the area of a complete directed graph on n...
An approximation scheme for some Steiner tree problems in the plane
An approximation scheme for some Steiner tree problems in the plane
1996,
We design a polynomial-time approximation scheme for the Steiner tree problem in the...
Optimally edge fault-tolerant trees
Optimally edge fault-tolerant trees
1996,
We study the structure of fault-tolerant multiprocessor systems that allow one or more...
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
1994,
We give a linear time and space algorithm for analyzing trees in planar graphs. The...
An algorithm for inverse minimm spanning tree problem
An algorithm for inverse minimm spanning tree problem
1997,
In this paper we consider an inverse minimum spanning tree problem in which we wish to...
Packing algorithms for arborescences (and spanning trees) in capacitated graphs
Packing algorithms for arborescences (and spanning trees) in capacitated graphs
1998,
In a digraph with real-valued edge capacities, we pack the greatest number of...
Designing reliable tree networks with two cable technologies
Designing reliable tree networks with two cable technologies
1998,
In this paper we introduce a minimal spanning tree problem with generalized hop...
An addendum to the hierarchical network design problem
An addendum to the hierarchical network design problem
1996,
The hierarchical network design problem is the problem to find a spanning tree of...
An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
1990,
Given n uniformly and independently distributed points in a ball of unit volume in...
A Lagrangean approach to the degree-constrained minimum spanning tree problem
A Lagrangean approach to the degree-constrained minimum spanning tree problem
1989,
A known branch and bound algorithm for the degree-constrained minimum spanning tree...
Papers per page: