The Steiner tree problem in orientation metrics

DOI10.1006/JCSS.1997.1513zbMATH Open0897.68076OpenAlexW1966114345MaRDI QIDQ1384537FDOQ1384537

Authors: D. Massart 

Publication date: 4 August 1998

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/fbb0690255acb8e23d7bb2044cebfa656d150917

Recommendations

• Efficient heuristics for orientation metric and Euclidean Steiner tree problems
• Steiner trees for fixed orientation metrics
• On the location of Steiner points in uniformly-oriented Steiner trees.
• Minimum networks in uniform orientation metrics

zbMATH Keywords

Steiner tree problemorientation metric

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• The Steiner tree problem
• Steiner Minimal Trees
• Steiner tree problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the Problem of Steiner
• How to find Steiner minimal trees in Euclidean \(d\)-space
• On Some Distance Problems in Fixed Orientations
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner’s Problem with Rectilinear Distance
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• Two probabilistic results on rectilinear Steiner trees
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• Subclass of the Steiner problems on a plane with rectilinear metric
• On the Steiner Problem
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Title not available (Why is that?)
• Rectilinear steiner trees: Efficient special-case algorithms
• Fast heuristic algorithms for rectilinear Steiner trees
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• A simple proof of Hwang's theorem for rectilinear Steiner minimal trees
• Title not available (Why is that?)
• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• A heuristic for Euclidean and rectilinear Steiner problems
• Rectilinear Steiner Trees in Rectangle Trees

Cited In (12)

• On the location of Steiner points in uniformly-oriented Steiner trees.
• Steiner trees for fixed orientation metrics
• Reducing the Steiner problem in four uniform orientations
• Rotationally optimal spanning and Steiner trees in uniform orientation metrics
• Angle-Restricted Steiner Arborescences for Flow Map Layout
• THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD
• Steiner hull algorithm for the uniform orientation metrics
• Steiner trees in general nonuniform orientations
• Minimum networks in uniform orientation metrics
• Title not available (Why is that?)
• A tight lower bound for planar Steiner orientation
• Forbidden subpaths for Steiner minimum networks in uniform orientation metrics

This page was built for publication: The Steiner tree problem in orientation metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384537)