Editing Steiner tree problem (section)

==References==
{{refbegin|30em}}
*{{cite conference
|last1= Berman |first1= Piotr
|last2= Karpinski |first2= Marek | authorlink2 = Marek Karpinski
|last3= Zelikovsky |first3= Alexander
|year= 2009
|contribution= 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2
|series= Lecture Notes in Computer Science
|title=Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21–23, 2009, Proceedings
|volume= 5664
|pages= 86–97
|doi=10.1007/978-3-642-03367-4_8
|arxiv= 0810.1851
|isbn= 978-3-642-03366-7
}}
*{{cite journal
|last1= Bern
|first1= Marshall W.
|last2= Graham
|first2= Ronald L. | author2-link = Ronald Graham
|year= 1989
|title= The shortest-network problem
|journal= Scientific American
|volume= 260
|pages= 84–89
|doi=10.1038/scientificamerican0189-84
|issue=1
|bibcode= 1989SciAm.260a..84B
}}
*{{cite conference
|last1=Björklund | first1=Andreas
|last2=Husfeldt | first2=Thore
|last3=Kaski | first3=Petteri
|last4=Koivisto | first4=Mikko
|year=2007
|contribution=Fourier Meets Möbius: Fast Subset Convolution
|title=[[Symposium on Theory of Computing|Proceedings of the 39th ACM Symposium on Theory of Computing]]
|pages=67–74
|doi=10.1145/1250790.1250801
|arxiv=cs/0611101| isbn=978-1-59593-631-8
}}
*{{cite conference|last1=Byrka|first1=J.|last2=Grandoni|first2=F.|last3=Rothvoß|first3=T.|last4=Sanita|first4=L.|year=2010|contribution=An improved LP-based approximation for Steiner tree|doi=10.1145/1806689.1806769|title = [[Symposium on Theory of Computing|Proceedings of the 42nd ACM Symposium on Theory of Computing]]|pages= 583–592 |isbn=978-1-4503-0050-6 |citeseerx=10.1.1.177.3565}}
*{{cite journal|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka|author2-link=Janka Chlebíková|year=2008|title=The Steiner tree problem on graphs: Inapproximability results|doi=10.1016/j.tcs.2008.06.046|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=406|issue=3|pages=207–214|doi-access=free}}
*{{cite conference
 | last1 = Chung | first1 = F. R. K. | author1-link = Fan Chung
 | last2 = Graham | first2 = R. L. | author2-link = Ronald Graham
 | contribution = A new bound for Euclidean Steiner minimal trees
 | doi = 10.1111/j.1749-6632.1985.tb14564.x
 | mr = 809217
 | pages = 328–346
 | publisher = New York Academy of Science | location = New York
 | series = Annals of the New York Academy of Science
 | title = Discrete geometry and convexity (New York, 1982)
 | volume = 440
 | year = 1985
 | bibcode = 1985NYASA.440..328C}}
*{{cite book |first=Dietmar|last=Cieslik |title=Steiner Minimal Trees |year=1998 |isbn=0-7923-4983-0 |pages=319|publisher=Springer }}
*{{Cite web
 | last1=Crescenzi | first1=Pierluigi
 | last2=Kann | first2=Viggo
 | last3=Halldórsson | first3=Magnús
 | last4=Karpinski | first4=Marek | authorlink4=Marek Karpinski
 | last5=Woeginger | first5=Gerhard | author5-link = Gerhard J. Woeginger
 | work=A Compendium of NP Optimization Problems
 | title=Minimum geometric Steiner tree
 | url=https://www.csc.kth.se/~viggo/wwwcompendium/node79.html
 | year=2000
 }}
*{{cite journal
|last1=Cygan | first1=Marek
|last2=Dell | first2=Holger
|last3=Lokshtanov | first3=Daniel
|last4=Marx | first4=Dániel
|last5=Nederlof | first5=Jesper
|last6=Okamoto | first6=Yoshio
|last7=Paturi | first7=Ramamohan
|last8=Saurabh | first8=Saket
|last9=Wahlström | first9=Magnus
|title=On Problems as Hard as CNF-SAT
|journal=ACM Transactions on Algorithms
| year=2016
|volume=12
|number=3
|pages=41:1–41:24
|doi=10.1145/2925416| s2cid=7320634
| url=http://eprints.sztaki.hu/9047/
|arxiv=1112.2275
}}
*{{cite journal
|last1=Dom | first1=Michael
|last2=Lokshtanov | first2=Daniel
|last3=Saurabh | first3=Saket
|title=Kernelization Lower Bounds Through Colors and IDs
|journal=ACM Transactions on Algorithms
|year=2014
|volume=11
|number=2
|pages=13:1–13:20
|doi=10.1145/2650261| s2cid=13570734
}}
*{{cite journal
|last1=Dreyfus | first1= S.E.
|last2=Wagner | first2 = R.A.
|year=1971
|title=The Steiner problem in graphs
|journal=Networks
|volume=1
|issue=3
|pages=195–207
|doi=10.1002/net.3230010302}}
*{{cite conference
|last1=Fomin | first1=Fedor V.
|last2=Kaski | first2=Petteri
|last3=Lokshtanov | first3=Daniel
|last4=Panolan | first4=Fahad
|last5=Saurabh | first5=Saket
|year=2015
|title=[[International Colloquium on Automata, Languages and Programming|Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Proceedings, Part I]]
| series=Lecture Notes in Computer Science
| volume=9134
|contribution=Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
|pages=494–505
|doi=10.1007/978-3-662-47672-7_40|hdl=1956/23311
| isbn=978-3-662-47671-0
|hdl-access=free
}}
*{{cite journal
|last1=Fuchs | first1=Benjamin
|last2=Kern | first2=Walter
|last3=Mölle | first3=Daniel
|last4=Richter | first4=Stefan
|last5=Rossmanith | first5=Peter
|last6=Wang | first6=Xinhui
|title=Dynamic Programming for Minimum Steiner Trees
|journal=Theory of Computing Systems
|year=2007
|volume=41
|issue=3
|pages=493–500
|doi=10.1007/s00224-007-1324-4| s2cid=7478978
| url=http://e-archive.informatik.uni-koeln.de/492/2/zaik2005-492.pdf
}}
*{{Cite book | first=Joseph L. | last=Ganley | url=https://xlinux.nist.gov/dads/HTML/steinerratio.html | contribution=Steiner ratio | title=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | year=2004 | access-date=2012-05-24 }}
* {{Garey-Johnson}}, {{Page numbers|208–209}}, problems ND12 and ND13.
*{{cite journal
 | last = Hwang | first = F. K.
 | doi = 10.1137/0130013
 | issue = 1
 | journal = SIAM Journal on Applied Mathematics
 | pages = 104–114
 | title = On Steiner minimal trees with rectilinear distance
 | volume = 30
 | year = 1976
 }}
* {{cite book |first1=F. K.|last1=Hwang|first2=D. S.|last2=Richards|first3=P.|last3=Winter |title=The Steiner Tree Problem |publisher=[[Elsevier]] |place=[[North-Holland Publishing Company|North-Holland]] |year=1992 |isbn=0-444-89098-X |series=Annals of Discrete Mathematics |volume=53}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Minimal Networks: The Steiner Problem and Its Generalizations |url= https://archive.org/details/minimalnetworkss0000ivan |url-access= registration |publisher=[[CRC Press]] |place=N.W., Boca Raton, Florida |year=1994 |isbn=978-0-8493-8642-8}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Branching solutions to one-dimensional variational problems |publisher=[[World Scientific]] |place=Singapore-New Jersey-London-Hong Kong |year=2000 |isbn=978-981-02-4060-8}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Extreme Networks Theory |place=Moscow-Izhevsk |publisher=Institute of Computer Investigations |year=2003 |language=Russian |isbn=5-93972-292-X}}
*{{cite journal
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement|journal=Algorithmica|year=2012|volume=62|issue=1–2|pages=630–632|doi=10.1007/s00453-011-9508-3|s2cid= 7486839
}}
*{{cite journal
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
|year= 2015
|title= Branched coverings and Steiner ratio
|journal= International Transactions in Operational Research
|volume= 23
|issue= 5
|pages= 875–882
|doi=10.1111/itor.12182
|arxiv=1412.5433|s2cid= 3386263
}}
*{{cite journal|last1=Juhl|first1=D.|last2=Warme|first2=D.M.|last3=Winter |first3=P.|last4=Zachariasen|first4=M.|title=The GeoSteiner Software Package for computing Steiner trees in the plane: an updated computational study|journal=  Mathematical Programming Computation|date=January 2018 |volume=10 |issue=4 |pages=487–532|doi=10.1007/s12532-018-0135-8|s2cid=255616114 |url=https://curis.ku.dk/portal/da/publications/the-geosteiner-software-package-for-computing-steiner-trees-in-the-plane(33ef119c-99c9-4511-9455-296ff28ee2eb).html }}
*{{cite journal|last1=Rehfeldt|first1=D.|last2=Koch|first2=T.|title=Implications, conflicts, and reductions for Steiner trees|journal= Mathematical Programming|date=February 2023 |volume=197|issue=2|pages=903–966|doi=10.1007/s10107-021-01757-5|s2cid=231842568 |doi-access=free}}
* {{cite conference
 | first1=Marek | last1=Karpinski
 | first2=Alexander | last2=Zelikovsky
 | contribution=Approximating dense cases of covering problems
 | pages=169–178
 | year=1998
 | contribution-url=https://books.google.com/books?id=IMmuF0RZk1MC&pg=PA169
 | title=Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location
 | publisher=American Mathematical Society
 | series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science
 | volume=40}}
*{{cite book
 | last1=Korte | first1=Bernhard | author1-link = Bernhard Korte
 | last2=Vygen | first2=Jens
 | title=Combinatorial Optimization: Theory and Algorithms
 | publisher=[[Springer Science+Business Media|Springer]]
 | year=2006
 | edition=3rd
 | isbn=3-540-25684-9
 | chapter=Section 20.1
}}
*{{cite journal |last1=Kou |first1=L. |last2=Markowsky |first2=G. |last3=Berman |first3=L. |title=A fast algorithm for Steiner trees |journal=Acta Informatica |date=1 June 1981 |volume=15 |issue=2 |pages=141–145 |doi=10.1007/BF00288961|s2cid=21057232 }}
*{{cite journal
|last1=Levin | first1=A. Yu.
|year=1971
|title=Algorithm for the shortest connection of a group of graph vertices
|journal=Soviet Mathematics Doklady
|volume=12
|pages=1477–1481}}
*{{cite conference
|last1 = Lokshtanov | first1=Daniel
|last2 = Nederlof | first2=Jesper
|contribution = Saving space by algebraization
|title=[[Symposium on Theory of Computing|Proceedings of the 42nd ACM Symposium on Theory of Computing]]
|year=2010
|pages=321–330
|doi=10.1145/1806689.1806735| isbn=978-1-4503-0050-6
}}
*{{cite journal|last1=Paolini|first1=E. |last2=Stepanov|first2=E.|title=Existence and regularity results for the Steiner problem|journal=Calc. Var. Partial Diff. Equations|year=2012|volume=46 |issue=3–4 |pages=837–860 |doi=10.1007/s00526-012-0505-4|hdl=2158/600141 |s2cid=55793499 |url=https://flore.unifi.it/bitstream/2158/600141/1/final-for-CalcVar.pdf|hdl-access=free}}
*{{cite conference
 | last1 = Robins
 | first1 = Gabriel
 | last2 = Zelikovsky
 | first2 = Alexander
 | contribution = Improved Steiner Tree Approximation in Graphs
 | contribution-url = http://dl.acm.org/citation.cfm?id=338219.338638
 | isbn = 0-89871-453-2
 | location = Philadelphia, PA, USA
 | pages = [https://archive.org/details/proceedingsofele0000acms/page/770 770–779]
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00)
 | year = 2000
 | url = https://archive.org/details/proceedingsofele0000acms/page/770
 }}
*{{cite book|title=Algorithms for VLSI Physical Design Automation|first=Naveed A.|last=Sherwani
| publisher = Kluwer Academic Publishers | year = 1993 | isbn = 9781475722192 }}
*{{cite book |editor1-first=Ding-Zhu|editor1-last=Du|editor2-first=Frank|editor2-last=Hwang |title=Computing in Euclidean geometry |publisher=World Scientific Publishing Co |location=River Edge, NJ |year=1995 |isbn=981-02-1876-1 |series=Lecture Notes Series on Computing |volume=4 | edition=2nd|contribution=Computational geometry and topological network design|first1=J. M.|last1=Smith|first2=P.|last2=Winter|pages=351–451}}
*{{cite journal |last1=Takahashi |first1=Hiromitsu |last2=Matsuyama |first2=Akira |title=An approximate solution for the Steiner problem in graphs |journal=Math. Japonica |date=1980 |volume=24 |issue=6 |pages=573–577}}
*{{cite book
 | last = Vazirani | first = Vijay V. | authorlink = Vijay Vazirani
 | title = Approximation Algorithms
 | publisher = Springer
 | year = 2003
 | place = Berlin
 | isbn = 3-540-65367-8
 }}
*{{cite book
 | last1=Wu | first1=Bang Ye
 | last2=Chao | first2=Kun-Mao
 | title=Spanning Trees and Optimization Problems
 | publisher=Chapman & Hall/CRC
 | year=2004
 | isbn=1-58488-436-3
 | chapter=Chapter 7
}}
*{{cite journal |last1=Wu |first1=Y. F. |last2=Widmayer |first2=P. |last3=Wong |first3=C. K. |title=A faster approximation algorithm for the Steiner problem in graphs |journal=Acta Informatica |date=May 1986 |volume=23 |issue=2 |pages=223–229 |doi=10.1007/bf00289500 |s2cid=7772232 }}
{{refend}}