Class Steiner trees and VLSI-design

DOI10.1016/S0166-218X(98)00090-0zbMath0921.68054MaRDI QIDQ1276969

Edmund Ihler, Peter Widmayer, Gabriele Reich

Publication date: 11 April 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Steiner problem in graphs

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (13)

A two-level metaheuristic for the all colors shortest path problem ⋮ Generalized minimum spanning tree games ⋮ How to sort by walking and swapping on paths and trees ⋮ An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ Solving group Steiner problems as Steiner problems. ⋮ MULTICASTING AND BROADCASTING IN UNDIRECTED WDM NETWORKS AND QoS EXTENTIONS OF MULTICASTING ⋮ Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances ⋮ Generalized network design problems. ⋮ The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm ⋮ Upper and lower bounding strategies for the generalized minimum spanning tree problem

Uses Software

• LEDA

Cites Work

• A note on two problems in connexion with graphs
• The Steiner problem with edge lengths 1 and 2
• A fast algorithm for Steiner trees
• Optimization, approximation, and complexity classes
• The Steiner tree problem
• The rectilinear class Steiner tree problem for intervals on two parallel lines
• Efficient probabilistic checkable proofs and applications to approximation
• Fibonacci heaps and their uses in improved network optimization algorithms
• A faster approximation algorithm for the Steiner problem in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Class Steiner trees and VLSI-design