Library

X
Language
Preferred search index
Number of Hits per Page
Default Sort Criterion
Default Sort Ordering
Size of Search History
Default Email Address
Default Export Format
Default Export Encoding
Facet list arrangement
Maximum number of values per filter
Auto Completion
Feed Format
Maximum Number of Items per Feed
Permalink If you want to be able to use settings permanently, you must save your settings and then set a Bookmark to the permalink
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Approximation Algorithms for Certain Network Improvement Problems (1998)
    Springer
    Journal of combinatorial optimization 2 (1998), S. 257-288 
    Details
    ISSN: 1573-2886
    Keywords: Complexity ; NP-hardness ; Approximation Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length ℓ(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009798010579
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...