Browse State-of-the-Art › Steiner Tree Problem

Steiner Tree Problem

8 papers with code · 0 benchmarks · 1 dataset archive 2025-07-28

Graphs

The Steiner tree problem is a computational problem in computer science and graph theory that involves finding the minimum weight subgraph in an undirected graph that connects a given set of terminal vertices. The goal of the Steiner tree problem is to minimize the total weight of the edges in the subgraph, and it is considered NP-hard, meaning that finding the optimal solution is computationally difficult.

Description from the archive archive 2025-07-28.

Benchmarks archive 2025-07-28

No benchmark for this task in the archive.

Libraries

Not in the archive: the export carries no per-task library table, so there is nothing to show at snapshot 2025-07-28.

Datasets archive 2025-07-28

1 dataset whose archive record lists this task, ordered by the archive's paper count.

Subtasks archive 2025-07-28

No subtask under this task in the archive's task tree.

Papers archive 2025-07-28

archive papers tagged: 17 · with a code link: 8 · where Syntology ran a sample: 1 (0 with a run with no instrument failure, 1 where every run was a failure of Syntology's instrument) Syntology

Show: all tagged papersonly where code ran (1 of 17 tagged: 0 with a run with no instrument failure, 1 where every run was a failure of Syntology's instrument)

Page 1 of 1: papers 1 to 17 of 17, in archive order: by repositories listed in the archive (most first), then newest first, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers that list no repository come after every paper that lists one.

Papers without a page here are shown as plain text. A Syntology line reads “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the figure “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code); hover it for the repositories the samples that ran came from.

  • With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems.
  • 3 Feb 2024 1 repository listed
    Considering a graph with unknown weights, can we find the shortest path for a pair of nodes if we know the minimal Steiner trees associated with some subset of nodes?
  • 22 Oct 2022 1 repository listed
    We apply our framework to three difficult problems on Euclidean space: the Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Routing Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem…
  • 20 Sep 2022 1 repository listed
    The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks.
  • 10 Dec 2021 1 repository listed
    Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable.
  • 15 Oct 2021 1 repository listed
    We create a novel Physarum Steiner algorithm designed to solve the Euclidean Steiner tree problem.
  • 9 Nov 2020 1 repository listed
    We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible heuristic function.
  • 28 Jun 2017 1 repository listed
    In this paper, we describe underlying concepts of our new implementation (DynASP2.
  • Learning to Prune Instances of Steiner Tree Problem in Graphs
    25 Aug 2022 0 repositories listed
    We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional…
  • Integrating connection search in graph queries
    9 Aug 2022 0 repositories listed
    Graph data management and querying has many practical applications.
  • Submarine Cable Network Design for Regional Connectivity
    15 Jan 2022 0 repositories listed
    This paper optimizes path planning for a trunkand-branch topology network in an irregular 2-dimensional manifold embedded in 3-dimensional Euclidean space with application to submarine cable network planning.
  • Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
    21 Nov 2021 0 repositories listed
    Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices.
  • Solving Large Steiner Tree Problems in Graphs for Cost-Efficient Fiber-To-The-Home Network Expansion
    22 Sep 2021 0 repositories listed
    The expansion of Fiber-To-The-Home (FTTH) networks creates high costs due to expensive excavation procedures.
  • Computing Steiner Trees using Graph Neural Networks
    18 Aug 2021 0 repositories listed
    Graph neural networks have been successful in many learning problems and real-world applications.
  • Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem
    18 Apr 2020 0 repositories listed
    This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem.
  • Evolutionary framework for two-stage stochastic resource allocation problems
    29 Nov 2018 0 repositories listed
    Resource allocation problems are a family of problems in which resources must be selected to satisfy given demands.
  • Solving the Steiner Tree Problem in graphs with Variable Neighborhood Descent
    13 Jun 2018 0 repositories listed
    The Steiner Tree Problem (STP) in graphs is an important problem with various applications in many areas such as design of integrated circuits, evolution theory, networking, etc.

Syntology lines on 1 of the papers shown; no Syntology record for the others (a paper without an arXiv id cannot be joined to the graph, and absence from the graph layer is not a recorded non-run). “Ran” means the sample executed on a synthesized fixture, not that the paper's result was reproduced; each line links to that paper's sample list. Syntology's record for this page last changed ; when this build read Syntology's graph is in the build record. For agents: get_harvested_code_for_paper(arxiv_id) lists each paper's samples; how to connect.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections