Concepedia

Steiner Tree Approximation

Steiner Tree Approximation is an approximation algorithm that belongs to the class of combinatorial optimization methods, specifically designed to find a near-optimal solution to the Steiner Tree Problem by minimizing the total edge weight of a tree interconnecting a given set of terminal vertices in a graph, allowing for the addition of non-terminal (Steiner) vertices to reduce overall cost.

424

Publications

28.3K

Citations

720

Authors

350

Institutions

Publications per year

2017–2026

37

Parents

Publications

424

Routing of multipoint connections

Bernard M. Waxman · IEEE Journal on Selected Areas in Communications · 1988 · 2.9K citations

, , +16

A fast algorithm for Steiner trees

Lawrence T. Kou, George Markowsky, L. Berman · Acta Informatica · 1981 · 1.2K citations

, , +8

An approximate solution for the Steiner problem in graphs

Haruhisa Takahashi, A Matsuyama · Mathematica japonica · 1980 · 884 citations

, , +10

A General Approximation Technique for Constrained Forest Problems

Michel X. Goemans, David P. Williamson · SIAM Journal on Computing · 1995 · 849 citations

, , +14

On Steiner trees and minimum spanning trees in hypergraphs

Tobias Polzin, Siavash Vahdati Daneshmand · Operations Research Letters · 2002 · 628 citations · Full text

, , +13

1–5 of 424

Authors

720

  1. AZ
    Alex Zelikovsky

    Georgia State University, United States

    12 publications · 1.9K citations

    12

    h-index

  2. RR
    R. Ravi

    Carnegie Mellon University, United States

    10 publications · 765 citations

    10

    h-index

  3. PN
    Philip N. Klein

    Brown University, United States

    9 publications · 430 citations

    9

    h-index

  4. GX
    Guoliang Xue

    Arizona State University, United States

    9 publications · 602 citations

    9

    h-index

  5. DD
    Ding‐Zhu Du

    The University of Texas at Dallas, United States

    9 publications · 449 citations

    9

    h-index

1–5 of 720

Institutions

350

  1. Massachusetts Institute of Technology

    Cambridge, United States

    14 h-index

    24 publications

    2.7K citations

  2. University of Waterloo

    Waterloo, Canada

    14 h-index

    22 publications

    1.3K citations

  3. University of Virginia

    Charlottesville, United States

    14 h-index

    21 publications

    2.1K citations

  4. AT&T (United States)

    Bedminster, United States

    13 h-index

    16 publications

    1.3K citations

  5. Princeton University

    Princeton, United States

    12 h-index

    13 publications

    1K citations

  6. Carnegie Mellon University

    Pittsburgh, United States

    12 h-index

    22 publications

    1.7K citations

  7. University of Minnesota

    Minneapolis, United States

    11 h-index

    21 publications

    1.1K citations

  8. Microsoft (United States)

    Redmond, United States

    10 h-index

    10 publications

    484 citations

1–8 of 350

Venues

  1. Algorithmica

    28 publications · 1.4K citations

    17

    h-index

  2. Discrete Applied Mathematics

    18 publications · 835 citations

    16

    h-index

  3. SIAM Journal on Computing

    15 publications · 1.5K citations

    13

    h-index

  4. Mathematical Programming

    13 publications · 1.3K citations

    13

    h-index

  5. Information Processing Letters

    15 publications · 1.1K citations

    12

    h-index

1–5