@string{ADM = {Annals of Discrete Mathematics}}
@string{ALG = {Algorithmica}}
@string{AOR = {Annals of Operations Research}}
@string{BSTJ = {Bell System Technical Journal}}
@string{CMA = {Computers and Mathematics with Applications}}
@string{DAM = {Discrete Applied Mathematics}}
@string{DCG = {Discrete and Computational Geometry}}
@string{DM = {Discrete Mathematics}}
@string{EJOR = {European Journal of Operational Research}}
@string{IEEETC = {{IEEE} Transactions on Computers}}
@string{IEEETCS = {{IEEE} Transactions on Circuits and Systems}}
@string{IJCGA = {International Journal of Computational Geometry and
Applications}}
@string{INTEGRATION = {Integration: the {VLSI} Journal}}
@string{IPL = {Information Processing Letters}}
@string{JALG = {Journal of Algorithms}}
@string{JCSS = {Journal of Computer and System Sciences}}
@string{JCTA = {Journal of Combinatorial Theory, Series~A}}
@string{JCTB = {Journal of Combinatorial Theory, Series~B}}
@string{LNCS = {Lecture Notes in Computer Science}}
@string{MPROG = {Mathematical Programming}}
@string{NWS = {Networks}}
@string{ORL = {Operations Research Letters}}
@string{RSA = {Random Structures and Algorithms}}
@string{SIAMJC = {{SIAM} Journal on Computing}}
@string{SIAMJAM = {{SIAM} Journal on Applied Mathematics}}
@string{SIAMJDM = {{SIAM} Journal on Discrete Mathematics}}
@string{SIAMJADM = {{SIAM} Journal on Algebraic and Discrete Methods}}
@string{TCAD = {{IEEE} Transactions on Computer-Aided Design}}
@string{TODAES = {{ACM} Transactions on Design Automation of
Electronic Systems}}
@article{AgarwalShing,
author = {P. K. Agarwal and M. I. Shing},
title = {Algorithms for the special cases of rectilinear {Steiner}
trees: {I}. {Points} on the boundary of a rectilinear
rectangle},
journal = NWS,
volume = 20,
year = 1990,
pages = {453--485}
}
@article{AhoGareyHwang,
author = {A. V. Aho and M. R. Garey and F. K. Hwang},
title = {Rectilinear {Steiner} trees: Efficient special-case
algorithms},
journal = NWS,
volume = 7,
year = 1977,
pages = {37--58}
}
@inproceedings{AlexanderRobins,
author = {M. J. Alexander and G. Robins},
title = {A new approach to {FPGA} routing based on multi-weighted graphs},
booktitle = {Proceedings of the International Workshop on
Field-Programmable Gate Arrays},
year = 1994
}
@inproceedings{AlexanderCohoonGanleyRobins,
author = {M. J. Alexander and J. P. Cohoon and J. L. Ganley and G. Robins},
title = {An architecture-independent approach to {FPGA} routing
based on multi-weighted graphs},
booktitle = {Proceedings of the European Design Automation Conference},
year = 1994,
pages = {259--264},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/euro_camera8_final.ps}
}
@inproceedings{AlexanderCohoonGanleyRobins95,
author = {M. J. Alexander and J. P. Cohoon and J. L. Ganley and G. Robins},
title = {Performance-oriented placement and routing for
field-programmable gate arrays},
booktitle = {Proceedings of the European Design Automation Conference},
year = 1995,
pages = {80--85},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/eurodac95_camerafinal.ps}
}
@article{AranovBernEppstein,
author = {B. Aronov and M. Bern and D. Eppstein},
title = {On the number of minimal {1-Steiner} trees},
journal = DCG,
year = 1994,
pages = {29--34},
url = {http://www.ics.uci.edu/\~{}eppstein/pubs/a-aronov.html}
}
@inproceedings{Arora,
author = {S. Arora},
title = {Polynomial-time approximation scheme for {Euclidean} {TSP}
and other geometric problems},
booktitle = {Proceedings of the Symposium on Foundations of
Computer Science},
year = 1996,
pages = {2--11},
abstract = {PTAS for Euclidean and rectilinear Steiner trees}
}
@book{Bakoglu,
author = {H. Bakoglu},
title = {Circuits, Interconnections, and Packaging for VLSI},
publisher = {Addison-Wesley},
address = {Reading, Massachusetts},
year = 1990
}
@phdthesis{Bapat,
author = {S. Bapat},
title = {A sharp methodology for {VLSI} layout},
school = {Department of Computer Science, University of Virginia},
address = {Charlottesville, Virginia},
year = 1993
}
@inproceedings{BapatCohoonHeckJuRandall,
author = {S. Bapat and J. P. Cohoon and P. L. Heck and
A. Ju and L. J. Randall},
title = {Examining routing solutions},
booktitle = {Proceedings of the Second Great Lakes Symposium
on {VLSI}},
month = {February},
year = 1992
}
@inproceedings{BapatCohoon,
author = {S. Bapat and J. P. Cohoon},
title = {A parallel {VLSI} circuit layout methodology},
booktitle = {Proceedings of the Sixth International Conference on
VLSI Design},
year = 1993,
pages = {236--241}
}
@inproceedings{BarrerraGriffithMckeeRobinsZhang,
author = {T. Barrerra and J. Griffith and S. A. McKee and
G. Robins and T. Zhang},
title = {Toward a {Steiner} engine: Enhanced serial and parallel
implementations of the iterated {1-Steiner} {MRST} heuristic},
booktitle = {Proceedings of the Third Great Lakes Symposium on VLSI},
year = 1992,
pages = {90--94}
}
@article{Beasley,
author = {J. E. Beasley},
title = {A heuristic for {Euclidean} and rectilinear {Steiner} problems},
journal = {European Journal of Operational Research},
volume = 58,
year = 1992,
pages = {284--292}
}
@article{BeasleySST,
author = {J. E. Beasley},
title = {An {SST}-based algorithm for the {Steiner} problem in graphs},
journal = NWS,
volume = 19,
year = 1989,
pages = {1--16}
}
@inproceedings{BermanRamaiyerConf,
author = {P. Berman and V. Ramaiyer},
title = {Improved approximations for the {Steiner} tree problem},
booktitle = {Proceedings of the Third Symposium on Discrete
Algorithms},
year = 1992,
pages = {325--334}
}
@article{BermanRamaiyer,
author = {P. Berman and V. Ramaiyer},
title = {Improved approximations for the {Steiner} tree problem},
journal = JALG,
volume = 17,
year = 1994,
pages = {381--408}
}
@article{Bern,
author = {M. Bern},
title = {Faster exact algorithms for {Steiner} trees in planar networks},
journal = NWS,
volume = 20,
year = 1990,
pages = {109--120}
}
@article{B88,
author = {M. W. Bern},
title = {Two probabilistic results on rectilinear {Steiner} trees},
journal = ALG,
year = 1988,
volume = 3,
pages = {191--204}
}
@inproceedings{BoeseKahngRobins,
author = {K. D. Boese and A. B. Kahng and G. Robins},
title = {High-performance routing trees with identified critical sinks},
booktitle = {Proceedings of the Thirtieth Design Automation Conference},
year = 1993,
pages = {182--187},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/csrt.ps}
}
@article{BoeseKahngMccoyRobins,
author = {K. D. Boese and A. B. Kahng and B. A. McCoy and G. Robins},
title = {Near-optimal critical sink routing tree constructions},
journal = TCAD,
year = 1995,
pages = {1417--1436},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/elmore_journal_final.ps}
}
@inproceedings{BoeseKahngMccoyRobinsICCD,
author = {K. D. Boese and A. B. Kahng and B. A. McCoy and G. Robins},
title = {Fidelity and near-optimality of {Elmore}-based routing
constructions},
booktitle = {Proceedings of the International Conference on
Computer Design},
year = 1993,
pages = {182--187},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/iccd_camera_final.ps}
}
@inproceedings{BoeseKahngMccoyRobinsSteiner,
author = {K. D. Boese and A. B. Kahng and B. A. McCoy and G. Robins},
title = {Rectilinear {Steiner} trees with minimum {Elmore} delay},
booktitle = {Proceeedings of the Design Automation Conference},
year = 1994,
pages = {381--386},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/dac94_camera7.ps}
}
@article{Booth,
author = {R. S. Booth},
title = {Analytic formulas for full {Steiner} trees},
journal = DCG,
volume = 6,
year = 1991,
pages = {69--82}
}
@article{BorchersDu,
author = {A. Borchers and {D.-Z.} Du},
title = {The $k$-{Steiner} ratio in graphs},
journal = SIAMJC,
volume = 26,
year = 1997,
pages = {857--869},
abstract = {Derives the Steiner ratio for $k$-restricted Steiner
trees in graphs, i.e. those in which no full tree
contains more than $k$ terminals.}
}
@article{Boyce,
author = {W. M. Boyce},
title = {An improved program for the full {Steiner} tree problem},
journal = {ACM Transactions on Mathematical Software},
volume = 3,
year = 1977,
pages = {359--385}
}
@techreport{BoyceSeery,
author = {W. M. Boyce and J. E. Seery},
title = {{STEINER} 72: An improved version of {Cockayne} and
{Schiller's} program {STEINER} for the minimal network problem},
number = 35,
institution = {Bell Laboratories},
address = {Murray Hill, New Jersey},
year = 1973
}
@article{BrazilColeRubinsteinThomasWengWormald,
author = {M. Brazil and T. Cole and J. H. Rubinstein and
D. A. Thomas and J. F. Weng and N. C. Wormald},
title = {Minimal Steiner trees for $2^k \times 2^k$ square lattices},
journal = JCTA,
volume = 72,
year = 1995
}
@techreport{BrazilRubinsteinWengWormaldThomas,
author = {M. Brazil and J. H. Rubinstein and D. A. Thomas and
J. F. Weng and N. C. Wormald},
title = {Full minimal Steiner trees on lattice sets},
institution = {Department of Mathematics, University of Melbourne},
number = {14-1995},
address = {Victoria, Australia},
year = 1995
}
@inproceedings{ChaoHsu,
author = {T. Chao and Y. Hsu},
title = {Rectilinear {Steiner} tree construction by local and global
refinement},
booktitle = {Proceedings of the International Conference
on Computer-Aided Design},
year = 1990,
pages = {432--435}
}
@techreport{Chen,
author = {D. S. Chen},
title = {Constrained wirelength minimization of a {Steiner} tree},
institution = {Department of Electrical Engineering and Computer
Science, Northwestern University},
address = {Evanston, Illinois},
year = 1994
}
@techreport{ChengLimWu,
author = {S. Cheng and A. Lim and C. Wu},
title = {Optimal rectilinear {Steiner} tree for extremal point sets},
institution = {Department of Computer Science, Hong Kong University
of Science and Technology},
number = {HKUST--CS93--6},
address = {Kowloon, Hong Kong},
month = {April},
year = 1993
}
@incollection{ChengLimWuISAAC,
author = {S. Cheng and A. Lim and C. Wu},
title = {Optimal rectilinear {Steiner} tree for extremal point sets},
booktitle = {Proceedings of the International Symposium on
Algorithms and Computation},
series = LNCS,
volume = 762,
publisher = {Springer-Verlag},
address = {Berlin, Germany},
year = 1993,
pages = {523--532}
}
@article {CWS94,
author = {C. Chiang and C. K. Wong and M. Sarrafzadeh},
title = {A weighted {Steiner} tree-based global router with simultaneous
length and density minimization},
journal = TCAD,
year = 1994,
pages = {1461--1469}
}
@article{ChiangSarrafzadehWongSwitchbox,
author = {C. Chiang and M. Sarrafzadeh and C. K. Wong},
title = {An algorithm for exact rectilinear {Steiner} trees for
switchbox with obstacles},
journal = IEEETCS,
volume = 39,
year = 1992,
pages = {446--455}
}
@article{ChiangSarrafzadehWongChannel,
author = {C. Chiang and M. Sarrafzadeh and C. K. Wong},
title = {An optimal algorithm for rectilinear {Steiner} trees for
channels with obstacles},
journal = {International Journal of Circuit Theory and Applications},
volume = 19,
year = 1991,
pages = {551--563}
}
@article{ChiangSarrafzadehWongMinmax,
author = {C. Chiang and M. Sarrafzadeh and C. K. Wong},
title = {Global routing based on {Steiner} min-max trees},
journal = TCAD,
volume = 9,
year = 1990,
pages = {1318--1325}
}
@inproceedings{Cho,
author = {{J.-D.} Cho},
title = {A min-cost flow base min-cost rectilinear {Steiner}
distance-preserving tree construction},
booktitle = {Proceedings of the International Symposium on Physical Design},
year = 1997,
pages = {82--87}
}
@article{ChopraRao1,
author = {S. Chopra and M. R. Rao},
title = {The {Steiner} tree problem 1: Formulations, compositions,
and extension of facets},
journal = MPROG,
volume = 64,
year = 1994,
pages = {209--229}
}
@article{ChopraRao2,
author = {S. Chopra and M. R. Rao},
title = {The {Steiner} tree problem 2: Properties and classes of facets},
journal = MPROG,
volume = 64,
year = 1994,
pages = {231--246}
}
@article{ChungGardnerGraham,
author = {F. R. K. Chung and M. Gardner and R. L. Graham},
title = {{Steiner} trees on a checkerboard},
journal = {Mathematics Magazine},
volume = 62,
year = 1989,
pages = {83--96}
}
@article{ChungGraham,
author = {F. R. K. Chung and R. L. Graham},
title = {{Steiner} trees for ladders},
journal = ADM,
volume = 2,
year = 1978,
pages = {173--200}
}
@article{CH78,
author = {F. R. K. Chung and F. K. Hwang},
title = {A lower bound for the {Steiner} tree problem},
journal = SIAMJAM,
year = 1978,
volume = 34,
pages = {27--36}
}
@article{ChungHwang,
author = {F. R. K. Chung and F. K. Hwang},
title = {The largest minimal rectilinear {Steiner} trees for a set
of~$n$ points enclosed in a rectangle with given perimeter},
journal = NWS,
volume = 9,
year = 1979,
pages = {19--36}
}
@inproceedings{CloutierBennour,
author = {J. Cloutier and I. Bennour},
title = {Topological characterization of {Hwang's} optimal
{Steiner} trees},
booktitle = {Proceedings of the Canadian Conference on
Computational Geometry},
year = 1993,
pages = {157--162}
}
@article{Cockayne,
author = {E. J. Cockayne},
title = {On the {Steiner} problem},
journal = {Canadian Mathematical Bulletin},
volume = 10,
year = 1967,
pages = {431--450}
}
@article{CockayneHewgill,
author = {E. J. Cockayne and D. E. Hewgill},
title = {Exact computation of {Steiner} minimal trees in the plane},
journal = IPL,
volume = 22,
year = 1986,
pages = {151--156}
}
@article{CockayneHewgillImproved,
author = {E. J. Cockayne and D. E. Hewgill},
title = {Improved computation of plane {Steiner} minimal trees},
journal = ALG,
volume = 7,
year = 1992,
pages = {219--229}
}
@article{CohoonRichardsSalowe,
author = {J. P. Cohoon and D. S. Richards and J. S. Salowe},
title = {An optimal {Steiner} tree algorithm for a net whose terminals
lie on the perimeter of a rectangle},
journal = TCAD,
volume = 9,
year = 1990,
pages = {398--407}
}
@inproceedings{CongLeungZhou,
author = {J. Cong and K. S. Leung and D. Zhou},
title = {Performance-driven interconnect design based on
distributed {RC} delay model},
booktitle = {Proceedings of the Thirtieth Design Automation Conference},
year = 1993,
pages = {606--611},
comment = {UCLA TR CSD--9200043, Sept 92}
}
@techreport{CordovaLee,
author = {J. C{\'o}rdova and {Y.-H.} Lee},
title = {A heuristic algorithm for the rectilinear {Steiner}
arborescence problem},
institution = {Computer and Information Sciences Department,
University of Florida},
number = {TR--94--025},
address = {Gainesville, Florida},
month = {August},
year = 1994
}
@article{DearingFrancis,
author = {P. M. Dearing and R. L. Francis},
title = {A network flow solution to a multifacility location
problem involving rectilinear distances},
journal = {Transportation Science},
volume = 8,
year = 1974,
pages = {126--141}
}
@inproceedings{DeneenDezell,
author = {L. L. Deneen and J. B. Dezell},
title = {Using partitioning and clustering techniques to generate
rectilinear {Steiner} trees},
booktitle = {Proceedings of the Second Canadian Conference on
Computational Geometry},
year = 1990,
pages = {315--318}
}
@article{DeneenShuteThomborson,
author = {L. L. Deneen and G. M. Shute and C. D. Thomborson},
title = {A probably fast, provably optimal algorithm for
rectilinear {Steiner} trees},
journal = {Random Structures and Algorithms},
volume = 5,
year = 1994,
pages = {535--557}
}
@article{DreznerWesolowsky,
author = {Z. Drezner and G. O. Wesolowsky},
title = {Layout of facilities with some fixed points},
journal = {Computers and Operations Research},
volume = 12,
year = 1985,
pages = {603--610}
}
@article{DreyfusWagner,
author = {S. E. Dreyfus and R. A. Wagner},
title = {The {Steiner} problem in graphs},
journal = NWS,
volume = 1,
year = 1972,
pages = {195--207}
}
@article{DuHwang,
author = {D. Z. Du and F. K. Hwang},
title = {A proof of the {Gilbert-Pollak} conjecture on the
{Steiner} ratio},
journal = ALG,
volume = 7,
year = 1992,
pages = {121--135}
}
@phdthesis{Duin,
author = {C. W. Duin},
title = {Steiner's problem in graphs: Approximation, reduction, estimation},
school = {Faculteit der Economische Wetenschappen en Econometrie,
Universiteit von Amsterdam},
address = {Amsterdam, The Netherlands},
year = 1993
}
@article{ElzingaHearnRandolph,
author = {J. Elzinga and D. Hearn and W. D. Randolph},
title = {Minimax multifacility location with {Euclidean} distances},
journal = {Transportation Science},
volume = 10,
year = 1976,
pages = {321--336}
}
@article{EricksonMonmaVeinott,
author = {R. E. Erickson and C. L. Monma and A. F. {Veinott Jr.}},
title = {Send-and-split method for minimum-concave-cost network flows},
journal = {Mathematics of Operations Research},
volume = 12,
year = 1987,
pages = {634--664}
}
@article{EysterWhite,
author = {J. W. Eyster and J. A. White},
title = {Some properties of the squared {Euclidean} distance
location problem},
journal = {AIIE Transactions},
volume = 5,
year = 1973,
pages = {275--280}
}
@inproceedings{FossmeierKaufmann,
author = {U. F{\"o}{\ss}meier and M. Kaufmann},
title = {Solving rectilinear {Steiner} tree problems exactly in
theory and practice},
booktitle = {Proceedings of the European Symposium on Algorithms},
year = 1997,
postscript = {http://www-pr.informatik.uni-tuebingen.de/\~{}mk/psfiles/esa97-steiner.ps.gz}
}
@inproceedings{FossmeierKaufmannZelikovsky,
author = {U. F{\"o}{\ss}meier and M. Kaufmann and A. Z. Zelikovsky},
title = {Faster approximation algorithms for the rectilinear {Steiner}
tree problem},
booktitle = {Proceedings of the 4th Annual International
Symposium on Algorithms and Computation},
series = LNCS,
volume = {??},
publisher = {Springer-Verlag},
year = 1993,
pages = {??}
}
@book{FrancisWhite,
author = {R. L. Francis and J. A. White},
title = {Facility Layout and Location: An Analytical Approach},
publisher = {Prentice-Hall},
address = {Englewood Cliffs, New Jersey},
year = 1974
}
@book{FrancisMcginnisWhite,
author = {R. L. Francis and L. F. McGinnis and J. A. White},
title = {Facility Layout and Location: An Analytical Approach},
publisher = {Prentice-Hall},
address = {Englewood Cliffs, New Jersey},
year = 1992
}
@phdthesis{Ganley,
author = {J. L. Ganley},
title = {Geometric Interconnection and Placement Algorithms},
school = {Department of Computer Science, University of Virginia},
address = {Charlottesville, Virginia},
year = 1995,
comment = {department #9503},
url = {ftp://ftp.cs.virginia.edu/pub/dissertations/9503_abs.html},
postscript = {ftp://ftp.cs.virginia.edu/pub/dissertations/9503.ps.Z},
pdf = {ftp://ftp.cs.virginia.edu/pub/dissertations/9503.pdf}
}
@inproceedings{GanleyCohoonGreatLakes,
author = {J. L. Ganley and J. P. Cohoon},
title = {A faster dynamic programming algorithm for exact rectilinear
{Steiner} minimal trees},
booktitle = {Proceedings of the Fourth Great Lakes Symposium on VLSI},
year = 1994,
pages = {238--241},
comment = {UVa TR CS-93-56},
abstract = {An O(n 3^n) algorithm for computing optimal
rectilinear Steiner trees}
}
@inproceedings{GanleyCohoonCCCG,
author = {J. L. Ganley and J. P. Cohoon},
title = {Optimal rectilinear {Steiner} minimal trees in~{$O(n^2 2.62^n)$}
time},
booktitle = {Proceedings of the Sixth Canadian Conference on
Computational Geometry},
year = 1994,
pages = {308--313},
abstract = {An O(n^2 2.62^n) algorithm for computing optimal
rectilinear Steiner trees}
}
@article{GanleyCohoonIJCGA,
author = {J. L. Ganley and J. P. Cohoon},
title = {Improved computation of optimal rectilinear Steiner
minimal trees},
journal = IJCGA,
year = 1997,
note = {(to appear)},
abstract = {An O(n 3^n) algorithm and an O(n^2 2.62^n) algorithm
for computing optimal rectilinear Steiner trees}
}
@inproceedings{GanleyCohoonISCAS,
author = {J. L. Ganley and J. P. Cohoon},
title = {Routing a multi-terminal critical net: {Steiner} tree
construction in the presence of obstacles},
booktitle = {Proceedings of the International Symposium on Circuits
and Systems},
year = 1994,
pages = {113--116},
abstract = {Proves an analogue of Hanan's theorem for rectilinear
Steiner trees in the presence of obstacles, and some
related results}
}
@inproceedings{GanleyCohoonThumbnail,
author = {J. L. Ganley and J. P. Cohoon},
title = {Thumbnail rectilinear {Steiner} trees},
booktitle = {Proceedings of the Fifth Great Lakes Symposium on VLSI},
year = 1995,
pages = {46--49},
comment = {UVa CS tech report CS-95-01},
abstract = {A full-set decomposition algorithm and other results
for rectilinear Steiner trees of terminals from a small
integer grid}
}
@article{GanleyCohoonThumbnailJournal,
author = {J. P. Cohoon and J. L. Ganley},
title = {Rectilinear {Steiner} trees on a checkerboard},
journal = TODAES,
volume = 1,
year = 1996,
comment = {number 4},
url = {http://www.acm.org/todaes/V1N4/L119/abstract.html},
postscript = {http://www.acm.org/todaes/V1N4/L119/paper.ps.gz},
pdf = {http://www.acm.org/todaes/V1N4/L119/paper.pdf},
abstract = {A full-set decomposition algorithm and other results
for rectilinear Steiner trees of terminals from a small
integer grid}
}
@incollection{CohoonGanleyChapter,
author = {J. P. Cohoon and J. L. Ganley},
title = {Rectilinear interconnections in the presence of obstacles},
booktitle = {Advanced Routing of Electronic Modules},
editor = {Y. T. Wong and M. Pecht},
publisher = {CRC Press},
address = {Boca Raton, Florida},
year = 1996
}
@article{GanleySaloweBottle,
author = {J. L. Ganley and J. S. Salowe},
title = {Optimal and approximate bottleneck {Steiner} trees},
journal = ORL,
volume = 19,
comment = {issue 5},
year = 1996,
pages = {217--224},
abstract = {An exact algorithm for Euclidean Steiner trees that
minimize the length of the longest edge, and the value
of the corresponding version of the Steiner ratio}
}
@article{GareyJohnsonRST,
author = {M. R. Garey and D. S. Johnson},
title = {The rectilinear {Steiner} tree problem is {NP}-complete},
journal = SIAMJAM,
volume = 32,
year = 1977,
pages = {826--834}
}
@article{GareyGrahamJohnson,
author = {M. R. Garey and R. L. Graham and D. S. Johnson},
title = {The complexity of computing {Steiner} minimal trees},
journal = SIAMJAM,
volume = 32,
year = 1977,
pages = {835--859},
abstract = {Proves that the Euclidean Steiner tree problem is NP-hard}
}
@article{GeorgakopoulosPapadimitriou,
author = {G. Georgakopoulos and C. H. Papadimitriou},
title = {The {1-Steiner} tree problem},
journal = JALG,
volume = 8,
year = 1987,
pages = {122--130}
}
@article{GilbertPollak,
author = {E. N. Gilbert and H. O. Pollak},
title = {Steiner minimal trees},
journal = SIAMJAM,
volume = 16,
year = 1966,
pages = {1--29}
}
@article{Goemans,
author = {M. X. Goemans},
title = {The {Steiner} tree polytope and related polyhedra},
journal = MPROG,
volume = 63,
year = 1994,
pages = {157--182}
}
@article{GoemansMyung,
author = {M. X. Goemans and Y. S. Myung},
title = {A catalog of {Steiner} tree formulations},
journal = NWS,
volume = 23,
year = 1993,
pages = {19--28}
}
@mastersthesis{Grimwood,
author = {G. R. Grimwood},
title = {The {Euclidean} {Steiner} tree problem: Simulated
annealing and other heuristics},
school = {Victoria University},
address = {Wellington, New Zealand},
year = 1994,
url = {http://www.isor.vuw.ac.nz/\~{}geoff/thesis.html},
postscript = {http://www.isor.vuw.ac.nz/\~{}geoff/CompressedThesis.ps.gz}
}
@article{GrotschelMartinWeismantel1,
author = {M. {Gr\"otschel} and A. Martin and R. Weismantel},
title = {Packing {Steiner} trees: Polyhedral investigations},
journal = MPROG,
volume = 72,
year = 1996,
pages = {101--123},
url = {http://www.zib.de/Optimization/node28.html#GroetschelMartinWeismantel96ABEGLMRWW1}
}
@article{GrotschelMartinWeismantel2,
author = {M. {Gr\"otschel} and A. Martin and R. Weismantel},
title = {Packing {Steiner} trees: A cutting plane algorithm and
computational results},
journal = MPROG,
volume = 72,
year = 1996,
pages = {125--145},
url = {http://www.zib.de/Optimization/node28.html#GroetschelMartinWeismantel96bABEGLMRWW1}
}
@article{Hakimi,
author = {S. L. Hakimi},
title = {{Steiner's} problem in graphs and its implications},
journal = NWS,
volume = 1,
year = 1971,
pages = {113--133}
}
@inproceedings{HasanVijayanWong,
author = {N. Hasan and G. Vijayan and C. K. Wong},
title = {A neighborhood improvement algorithm for rectilinear
{Steiner} trees},
booktitle = {Proceedings of the International Symposium on
Circuits and Systems},
year = 1990,
pages = {2869--2872}
}
@article{Hanan,
author = {M. Hanan},
title = {On {Steiner's} problem with rectilinear distance},
journal = SIAMJAM,
volume = 14,
year = 1966,
pages = {255--265}
}
@inproceedings{HesserMannerStucky,
author = {Hesser and Manner and Stucky},
title = {Optimisation of {Steiner} trees using genetic algorithms},
booktitle = {Proceedings of the Third International
Conference on Genetic Algorithms},
year = 1989
}
@inproceedings{HightowerSurvey,
author = {D. W. Hightower},
title = {The interconnection problem---a tutorial},
booktitle = {Proceedings of the Tenth Design Automation Workshop},
year = 1973,
pages = {1--21}
}
@article{HoVijayanWong,
author = {J. Ho and G. Vijayan and C. K. Wong},
title = {New algorithms for the rectilinear {Steiner} tree problem},
journal = TCAD,
volume = 9,
year = 1990,
pages = {185--193}
}
@inproceedings{HongXueKuhChengHuang,
author = {X. Hong and T. Xue and E. S. Kuh and {C.-K.} Cheng and J. Huang},
title = {Performance-driven {Steiner} tree algorithms for global routing},
booktitle = {Proceedings of the Thirtieth Design Automation Conference},
year = 1993,
pages = {177--181}
}
@article{Hooker,
author = {J. N. Hooker},
title = {Solving nonlinear multiple-facility network location problems},
journal = NWS,
volume = 19,
year = 1989,
pages = {117--133}
}
@article{Hwang,
author = {F. K. Hwang},
title = {On {Steiner} minimal trees with rectilinear distance},
journal = SIAMJAM,
volume = 30,
year = 1976,
pages = {104--114}
}
@article{HwangEuclidean,
author = {F. K. Hwang},
title = {A linear time algorithm for full {Steiner} trees},
journal = ORL,
volume = 4,
year = 1986,
pages = {235--237}
}
@article{Hwa79a,
author = {F. K. Hwang},
title = {An $O(n log n)$ algorithm for rectilinear minimal
spanning trees},
journal = JACM,
volume = 26,
year = 1979,
pages = {177--182}
}
@article{HwangDu,
author = {F. K. Hwang and D. Z. Du},
title = {{Steiner} minimal trees on the {Chinese} checkerboard},
journal = {Mathematics Magazine},
volume = 64,
year = 1991,
pages = {332--339}
}
@book{HwangRichardsWinter,
author = {F. K. Hwang and D. S. Richards and P. Winter},
title = {The {Steiner} Tree Problem},
series = ADM,
volume = 53,
publisher = {North-Holland},
address = {Amsterdam, Netherlands},
year = 1992
}
@article{HwangChangLee,
author = {R. Z. Hwang and R. C. Chang and R. C. T. Lee},
title = {The searching over separators strategy to solve some
{NP}-hard problems in subexponential time},
journal = ALG,
volume = 9,
year = 1993,
pages = {398-423}
}
@article{HY90,
author = {F. K. Hwang and Y. C. Yao},
title = {Comments on {Bern's} probabilistic results on rectilinear
{Steiner} trees},
journal = ALG,
year = 1990,
volume = 5,
pages = {591--598},
}
@article{Ichimori,
author = {T. Ichimori},
title = {A shortest path approach to a multifacility minimax
location problem with rectilinear distances},
journal = {Journal of the Operations Research Society of Japan},
volume = 28,
year = 1985,
pages = {269--284}
}
@techreport{IhlerLines,
author = {E. Ihler},
title = {The rectilinear class {Steiner} tree problem for intervals
on two parallel lines},
institution = {Institut f\"ur Informatik, Universit\"at Freiburg},
address = {Freiburg, Germany},
number = {47},
year = 1993,
postscript = {ftp://ftp.informatik.uni-freiburg.de/documents/reports/report47/report47.ps.gz}
}
@techreport{IhlerApprox,
author = {E. Ihler},
title = {The complexity of approximating the class {Steiner} tree problem},
institution = {Institut f\"ur Informatik, Universit\"at Freiburg},
address = {Freiburg, Germany},
number = {32},
year = 1991,
postscript = {ftp://ftp.informatik.uni-freiburg.de/documents/reports/report32/report32.ps.gz}
}
@techreport{IhlerGroup,
author = {E. Ihler},
title = {Bounds on the quality of approximate solutions to the
group {Steiner} problem},
institution = {Institut f\"ur Informatik, Universit\"at Freiburg},
address = {Freiburg, Germany},
number = {23},
year = 1990,
postscript = {ftp://ftp.informatik.uni-freiburg.de/documents/reports/report23/report23.ps.gz}
}
@book{IvanovTuzhelin,
author = {A. O. Ivanov and A. A. Tuzhelin},
title = {Minimal networks: The {Steiner} problem and its generalizations},
publisher = {CRC Press},
year = 1994
}
@inproceedings{Julstrom,
author = {B. A. Julstrom},
title = {A genetic algorithm for the rectilinear {Steiner} problem},
booktitle = {Proceedings of the Fifth International
Conference on Genetic Algorithms},
year = 1993
}
@article{KahngRobins,
author = {A. B. Kahng and G. Robins},
title = {A new class of iterative {Steiner} tree heuristics with
good performance},
journal = TCAD,
volume = 11,
year = 1992,
pages = {893--902}
}
@book{KahngRobinsBook,
author = {A. B. Kahng and G. Robins},
title = {On Optimal Interconnections for VLSI},
publisher = {Kluwer Academic Publishers},
address = {Norwell, Massachusetts},
year = 1995
}
@article{KahngRobinsBounds,
author = {A. B. Kahng and G. Robins},
title = {On performance bounds for a class of rectilinear {Steiner} tree
heuristics in arbitrary dimension},
journal = TCAD,
volume = 11,
year = 1992
}
@article{KalpakisSherman,
author = {K. Kalpakis and A. T. Sherman},
title = {Probabilistic analysis of an enhanced partitioning
algorithm for the {Steiner} problem in {$R^d$}},
journal = NWS,
volume = 24,
year = 1994,
pages = {147--159},
url = {http://www.cs.umbc.edu/\~{}sherman/Rtopics/Algs/steiner.html},
postscript = {http://www.cs.umbc.edu/pub/REPORTS/cs-93-10.ps}
}
@article{KapsalisRaywardsmithSmith,
author = {Firstname Kapsalis and Firstname {Rayward-Smith} and
Firstname Smith},
title = {Solving the graphical {Steiner} tree problem using genetic
algorithms},
journal = {Journal of the Operational Research Society},
volume = 44,
year = 1993
}
@article{Karp,
author = {R. M. Karp},
title = {On the computational complexity of combinatorial problems},
journal = NWS,
volume = 5,
year = 1975,
pages = {45--68}
}
@incollection{KaufmannGaoThulasiraman,
author = {M. Kaufmann and S. Gao and K. Thulasiraman},
title = {On {Steiner} minimal trees in grid graphs and its
application to {VLSI} layout},
booktitle = {Proceedings of the International Symposium on
Algorithms and Computation},
series = LNCS,
volume = 834,
publisher = {Springer-Verlag},
address = {Berlin, Germany},
year = 1994,
pages = {351--359}
}
@article{KleinRavi,
author = {P. Klein and R. Ravi},
title = {A nearly best-possible approximation algorithm for
node-weighted {Steiner} trees},
journal = JALG,
volume = 19,
year = 1995,
pages = {104--115}
}
@techreport{KochMartin,
author = {T. Koch and A. Martin},
title = {Solving {Steiner} tree problems in graphs to optimality},
institution = {Konrad-Zuse-Zentrum f\"ur Informationstechnik},
number = {{SC} 96--42},
address = {Berlin, Germany},
year = 1996,
url = {http://www.zib.de/Optimization/node28.html#KochMartin96GABEGLMRWW1},
postscript = {ftp://ftp.zib.de/pub/zib-publications/reports/SC-96-42.ps}
}
@mastersthesis{Koh,
author = {C. K. Koh},
title = {{Steiner} problem in octilinear routing model},
school = {National University of Singapore},
year = 1995,
url = {http://ballade.cs.ucla.edu:8080/\~{}kohck/papers/abstract.html#steiner},
postscript = {http://ballade.cs.ucla.edu:8080/\~{}kohck/papers/steiner/steiner.ps.Z}
}
@article{KomlosShing,
author = {J. Koml{\'o}s and M. T. Shing},
title = {Probabilistic partitioning algorithms for the rectilinear
{Steiner} problem},
journal = NWS,
volume = 15,
year = 1985,
pages = {413--423}
}
@incollection{KortePromelSteger,
author = {B. Korte and H. J. {Pr\"omel} and A. Steger},
title = {Steiner trees in {VLSI}-layout},
booktitle = {Paths, Flows, and {VLSI}-Layout},
editor = {B. Korte and L. {Lov\'asz} and H. J. {Pr\"omel} and A. Schrijver},
publisher = {Springer-Verlag},
address = {Berlin, Germany},
year = 1990,
pages = {185--214}
}
@article{KMB81,
author = {L. Kou and G. Markowsky and L. Berman},
title = {A fast algorithm for {Steiner} trees},
journal = {Acta Informatica},
year = 1981,
volume = 15,
pages = {141--145},
}
@phdthesis{Ladeiradematos,
author = {R. R. {Ladeira de Matos}},
title = {A rectilinear arborescence problem},
school = {Department of Engineering Production, University of Birmingham},
address = {Birmingham, England},
year = 1979
}
@article{LeeBoseHwang,
author = {J. H. Lee and N. K. Bose and F. K. Hwang},
title = {Use of {Steiner's} problem in suboptimal routing in
rectilinear metric},
journal = IEEETCS,
year = 1976,
pages = {470--476}
}
@book{Lengauer,
author = {T. Lengauer},
title = {Combinatorial algorithms for integrated circuit layout},
publisher = {Wiley \& Sons},
address = {New York, New York},
year = 1990
}
@inproceedings{LewisPongVancleave,
author = {F. D. Lewis and W. C. Pong and N. {Van Cleave}},
title = {Optimum {Steiner} tree generation},
booktitle = {Proceedings of the Second Great Lakes Symposium on VLSI},
year = 1992,
pages = {207--212}
}
@article{LoveWesolowskyKraemer,
author = {R. F. Love and G. O. Wesolowsky and S. A. Kraemer},
title = {A multifacility minimax location method for {Euclidean}
distances},
journal = {International Journal of Production Research},
volume = 11,
year = 1973,
pages = {37--45}
}
@article{Melzak,
author = {Z. A. Melzak},
title = {On the problem of {Steiner}},
journal = {Canadian Mathematics Bulletin},
volume = 4,
year = 1961,
pages = {143--149}
}
@article{MikamiTabuchi,
author = {K. Mikami and K. Tabuchi},
title = {A computer program for optimal routing of printed circuit
connectors},
journal = {IFIPS Proceedings},
volume = {H47},
year = 1968,
pages = {1475--1478}
}
@inproceedings{MST90,
author = {T. Matsumoto and N. Saigan and K. Tsuji},
title = {A new efficient approximation algorithm for the {Steiner} tree
problem in rectilinear graph},
booktitle = {Proceedings of the IEEE International Symposium on
Circuits and Systems},
year = 1990,
pages = {2874-2876}
}
@inproceedings{MirayalaHashmiSherwani,
author = {S. Mirayala and J. Hashmi and N. Sherwani},
title = {Switchbox {Steiner} tree problem in presence of obstacles},
booktitle = {Proceedings of the International Conference on
Computer-Aided Design},
year = 1991,
pages = {536--539}
}
@inproceedings{NgRaghavanThompson,
author = {A. Ng and P. Raghavan and C. D. Thompson},
title = {A language for describing rectilinear {Steiner} tree
configurations},
booktitle = {Proceedings of the Twenty-third Design Automation Conference},
year = 1986,
pages = {574--580}
}
@article{Prodon,
author = {Firstname Prodon},
title = {Steiner trees with~$n$ terminals among~$n+1$ nodes},
journal = ORL,
volume = 11,
year = 1992,
pages = {125--133},
comment = {polyhedral results}
}
@incollection{PromelSteger,
author = {H. J. {Pr\"omel} and A. Steger},
title = {{RNC}-approximation algorithms for the {Steiner} problem},
booktitle = {Proceedings of the Symposium on Theoretical Aspects of
Computer Science},
series = LNCS,
volume = 1200,
editor = {R. Reischuk and M. Morvan},
publisher = {Springer-Verlag},
address = {Berlin, Germany},
year = 1997,
pages = {559--570}
}
@article{Provan,
author = {J. S. Provan},
title = {Convexity and the {Steiner} tree problem},
journal = NWS,
volume = 18,
year = 1988,
pages = {55--72}
}
@techreport{ProvanTR,
author = {J. S. Provan},
title = {A polynomial algorithm for the {Steiner} tree problem on
terminal-planar graphs},
institution = {Department of Operations Research, University of
North Carolina},
number = {83/10},
address = {Chapel Hill, North Carolina},
year = 1983
}
@article{RaoSadayappanHwangShor,
author = {S. K. Rao and P. Sadayappan and F. K. Hwang and P. W. Shor},
title = {The rectilinear {Steiner} arborescence problem},
journal = ALG,
volume = 7,
year = 1992,
pages = {277--288}
}
@article{RavadaSherman,
author = {S. Ravada and A. T. Sherman},
title = {Experimental evaluation of a partitioning algorithm for
the {Steiner} tree problem in {$R^2$} and {$R^3$}},
journal = NWS,
note = {(to appear)},
url = {http://www.cs.umbc.edu/\~{}sherman/Rtopics/Algs/steiner.html},
postscript = {http://www.cs.umbc.edu/pub/REPORTS/cs-93-12.ps}
}
@unpublished{Richards,
author = {D. S. Richards},
title = {On the effectiveness of greedy heuristics for the
rectilinear {Steiner} problem},
note = {manuscript},
year = 1991
}
@article{Ric89,
author = {Dana Richards},
title = {Fast heuristic algorithms for rectilinear {Steiner} trees},
journal = ALG,
year = 1989,
volume = 4,
pages = {191--207}
}
@article{RichardsSalowe,
author = {D. S. Richards and J. S. Salowe},
title = {A linear-time algorithm to construct a rectilinear
{Steiner} minimal tree for $k$-extremal point sets},
journal = ALG,
volume = 7,
year = 1992,
pages = {247--276}
}
@article{RichardsSaloweFulltree,
author = {D. S. Richards and J. S. Salowe},
title = {A simple proof of {Hwang's} theorem for rectilinear {Steiner}
minimal trees},
journal = AOR,
volume = 33,
year = 1991,
pages = {549--556}
}
@inproceedings{RobinsSalowe,
author = {G. Robins and J. S. Salowe},
title = {On the maximum degree of minimum spanning trees},
booktitle = {Proceedings of the ACM Symposium on Computational Geometry},
year = 1994,
pages = {250--258},
postscript = {http://www.cs.virginia.edu/\~{}robins/papers/cg94_camera3_final.ps}
}
@unpublished{Salowe,
author = {J. S. Salowe},
title = {On exact algorithms for rectilinear {Steiner} minimal trees},
note = {unpublished manuscript},
year = 1992
}
@inproceedings{SaloweWarmeConf,
author = {J. S. Salowe and D. M. Warme},
title = {An exact rectilinear {Steiner} tree algorithm},
booktitle = {Proceedings of the International Conference on
Computer Design},
year = 1993,
pages = {472--475}
}
@article{SaloweWarme,
author = {J. S. Salowe and D. M. Warme},
title = {35-point rectilinear {Steiner} minimal trees in a day},
journal = NWS,
volume = 25,
pages = {69--87},
year = 1995
}
@book{SarrafzadehWongBook,
author = {M. Sarrafzadeh and C. K. Wong},
title = {An Introduction to VLSI Physical Design},
publisher = {McGraw-Hill},
year = 1996
}
@article{SarrafzadehWong,
author = {M. Sarrafzadeh and C. K. Wong},
title = {Bottleneck {Steiner} trees in the plane},
journal = IEEETC,
volume = 41,
year = 1992,
pages = {370--374}
}
@article{SW90,
author = {M. Sarrafzadeh and C. K. Wong},
title = {Hierarchical {Steiner} tree construction in uniform
orientations},
journal = TCAD,
volume = 11,
year = 1992,
pages = {1095--1103},
}
@unpublished{SW91b,
author = {M. Sarrafzadeh and C. K. Wong},
title = {New directions in the rectilinear {Steiner} tree problem},
note = {manuscript},
year = 1991
}
@article{ShoreFouldsGibbons,
author = {M. L. Shore and L. R. Foulds and P. B. Gibbons},
title = {An algorithm for the {Steiner} problem in graphs},
journal = NWS,
volume = 12,
year = 1982,
pages = {323--333}
}
@article{Sidorenko,
author = {A. F. Sidorenko},
title = {On minimal rectilinear {Steiner} trees},
journal = {Diskretnaya Matematika},
volume = 1,
year = 1989,
pages = {28--37},
note = {(In Russian)}
}
@article{Smith,
author = {W. D. Smith},
title = {How to find {Steiner} minimal trees in {Euclidean} $d$-space},
journal = ALG,
volume = 7,
year = 1992,
pages = {137--177}
}
@article{SmithLeeLiebman,
author = {J. M. Smith and D. T. Lee and J. S. Liebman},
title = {An {$O(n \log n)$} heuristic algorithm for the rectilinear
{Steiner} minimal tree problem},
journal = {Engineering Optimization},
volume = 4,
year = 1980,
pages = {179--192}
}
@article{SmithLiebman,
author = {J. M. Smith and J. S. Liebman},
title = {{Steiner} trees, {Steiner} circuits, and the interference
problem in building design},
journal = {Engineering Optimization},
volume = 4,
year = 1979,
pages = {15--36}
}
@article{Sny91,
author = {T. L. Snyder},
title = {Lower bounds for rectilinear {Steiner} trees in bounded space},
journal = IPL,
volume = 37,
year = 1991,
pages = {71--74}
}
@article{Soukup,
author = {J. Soukup},
title = {On minimum cost networks with nonlinear costs},
journal = SIAMJAM,
volume = 29,
year = 1975,
pages = {571--581}
}
@inproceedings{San90,
author = {H. Suzuki, T. Akama and T. Nishizeki},
title = {Finding {Steiner} forests in planar graphs},
booktitle = {Proceedings of the First Annual ACM-SIAM Symposium on
Discrete Algorithms},
year = 1990,
pages = {444-453}
}
@article{TanselFrancisLowe,
author = {B. C. Tansel and R. L. Francis and T. J. Lowe},
title = {Location on networks: A survey; part {I}: The $p$-center
and $p$-median problems},
journal = {Management Science},
volume = 29,
year = 1983,
pages = {482--497}
}
@incollection{ThomborsonAlpernCarter,
author = {C. D. Thomborson and B. Alpern and L. Carter},
title = {Rectilinear {Steiner} tree minimization on a workstation},
booktitle = {Computational Support for Discrete Mathematics},
series = {DIMACS Series in Discrete Mathematics and Theoretical
Computer Science},
volume = 15,
editor = {N. Dean and G. E. Shannon},
publisher = {American Mathematical Society},
address = {Providence, Rhode Island},
year = 1994,
pages = {119--136}
}
@incollection{ThomborsonDeneenShute,
author = {C. D. Thomborson and L. L. Deneen and G. M. Shute},
title = {Computing a rectilinear {Steiner} minimal tree in
{$O(n^{O(\sqrt{n})})$} time},
booktitle = {Parallel Algorithms and Architectures},
series = LNCS,
volume = 269,
editor = {A. Albrecht and K. Mehlhorn},
publisher = {Springer-Verlag},
address = {Berlin, Germany},
year = 1987,
pages = {176--183}
}
@article{White,
author = {J. A. White},
title = {A quadratic facility location problem},
journal = {AIIE Transactions},
volume = 3,
year = 1971,
pages = {156--157}
}
@article{Winter,
author = {P. Winter},
title = {An algorithm for the {Steiner} problem in the {Euclidean} plane},
journal = NWS,
volume = 15,
year = 1985,
pages = {323--345}
}
@article{Win87,
author = {P. Winter},
title = {Steiner Problem in Networks: A Survey},
journal = NWS,
volume = 17,
year = 1987,
pages = {129--167}
}
@article{WinterObstacles,
author = {P. Winter},
title = {Euclidean {Steiner} minimal trees with obstacles and
{Steiner} visibility graphs},
journal = DAM,
volume = 47,
year = 1993,
pages = {187--206}
}
@unpublished{WinterReductions,
author = {P. Winter},
title = {Reductions for the rectilinear {Steiner} tree problem},
note = {manuscript},
year = 1994
}
@mastersthesis{Wong,
author = {Y. T. Wong},
title = {{Steiner} Tree Oriented Placement},
school = {Department of Mechanical Engineering, University of Maryland},
address = {College Park, Maryland},
year = 1988
}
@article{WongPechtJEP,
author = {Y. T. Wong and M. Pecht},
title = {Approximating the {Steiner} tree in the placement process},
journal = {Journal of Electronic Packaging},
volume = 111,
year = 1989,
pages = {228--235}
}
@incollection{WongPecht,
author = {Y. T. Wong and M. Pecht},
title = {A solution for {Steiner's} problem},
booktitle = {Placement and Routing of Electronic Modules},
editor = {M. Pecht},
publisher = {Marcel Dekker},
address = {New York, New York},
year = 1993,
pages = {261--304}
}
@inproceedings{YangWing,
author = {Y. Y. Yang and O. Wing},
title = {Optimal and suboptimal solution algorithms for the wiring problem},
booktitle = {Proceedings of the International Symposium on Circuit Theory},
year = 1972,
pages = {154--158}
}
@article{Yao82,
author = {A. C. Yao},
title = {On constructing minimum spanning trees in $k$-dimensional
spaces and related problems},
journal = SIAMJC,
volume = 11,
year = 1982,
pages = {721-736}
}
@inproceedings{ZelikovskyConf,
author = {A. Z. Zelikovsky},
title = {An $11/6$-approximation algorithm for the {Steiner}
problem on graphs},
booktitle = {Proceedings of the Fourth Czechoslovakian Symposium on
Combinatorics, Graphs, and Complexity},
year = 1992,
pages = {351--354}
}
@article{ZelikovskyIPL,
author = {A. Z. Zelikovsky},
title = {A faster approximation algorithm for the {Steiner} tree
problem in graphs},
journal = IPL,
volume = 46,
year = 1993,
pages = {79--83}
}
@article{Zelikovsky,
author = {A. Z. Zelikovsky},
title = {An $11/6$-approximation algorithm for the network
{Steiner} problem},
journal = ALG,
volume = 9,
year = 1993,
pages = {463--470}
}