Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem Article Swipe
Reyan Ahmed
,
Faryad Darabi Sahneh
,
Keaton Hamm
,
Stephen Kobourov
,
Richard Spence
·
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2020.4
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2020.4
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln |T|+1), 𝓁 ρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and 𝓁 is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
Related Topics
Concepts
Steiner tree problem
Combinatorics
Approximation algorithm
Mathematics
Generalization
k-minimum spanning tree
Gomory–Hu tree
Tree (set theory)
Spanning tree
Discrete mathematics
Greedy algorithm
Solver
Minimum spanning tree
K-ary tree
Mathematical optimization
Tree structure
Binary tree
Mathematical analysis
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4
- OA Status
- green
- Cited By
- 2
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W3082850793
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3082850793Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.esa.2020.4Digital Object Identifier
- Title
-
Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree ProblemWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2020Year of publication
- Publication date
-
2020-01-01Full publication date if available
- Authors
-
Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard SpenceList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4Direct OA link when available
- Concepts
-
Steiner tree problem, Combinatorics, Approximation algorithm, Mathematics, Generalization, k-minimum spanning tree, Gomory–Hu tree, Tree (set theory), Spanning tree, Discrete mathematics, Greedy algorithm, Solver, Minimum spanning tree, K-ary tree, Mathematical optimization, Tree structure, Binary tree, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
2Total citation count in OpenAlex
- Citations by year (recent)
-
2021: 2Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3082850793 |
|---|---|
| doi | https://doi.org/10.4230/lipics.esa.2020.4 |
| ids.doi | https://doi.org/10.4230/lipics.esa.2020.4 |
| ids.mag | 3082850793 |
| ids.openalex | https://openalex.org/W3082850793 |
| fwci | 0.29494429 |
| type | article |
| title | Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | 21 |
| topics[0].id | https://openalex.org/T11606 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9902999997138977 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2205 |
| topics[0].subfield.display_name | Civil and Structural Engineering |
| topics[0].display_name | Infrastructure Maintenance and Monitoring |
| topics[1].id | https://openalex.org/T10720 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9765999913215637 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Complexity and Algorithms in Graphs |
| topics[2].id | https://openalex.org/T11522 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9627000093460083 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2208 |
| topics[2].subfield.display_name | Electrical and Electronic Engineering |
| topics[2].display_name | VLSI and FPGA Design Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C76220878 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9160599708557129 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1764144 |
| concepts[0].display_name | Steiner tree problem |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6985397338867188 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C148764684 |
| concepts[2].level | 2 |
| concepts[2].score | 0.697677731513977 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[2].display_name | Approximation algorithm |
| concepts[3].id | https://openalex.org/C33923547 |
| concepts[3].level | 0 |
| concepts[3].score | 0.6701760292053223 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[3].display_name | Mathematics |
| concepts[4].id | https://openalex.org/C177148314 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5517899990081787 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q170084 |
| concepts[4].display_name | Generalization |
| concepts[5].id | https://openalex.org/C202750272 |
| concepts[5].level | 5 |
| concepts[5].score | 0.5415838360786438 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q6322849 |
| concepts[5].display_name | k-minimum spanning tree |
| concepts[6].id | https://openalex.org/C147517495 |
| concepts[6].level | 5 |
| concepts[6].score | 0.48628342151641846 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q5581241 |
| concepts[6].display_name | Gomory–Hu tree |
| concepts[7].id | https://openalex.org/C113174947 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4763203561306 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2859736 |
| concepts[7].display_name | Tree (set theory) |
| concepts[8].id | https://openalex.org/C64331007 |
| concepts[8].level | 2 |
| concepts[8].score | 0.45546942949295044 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q831672 |
| concepts[8].display_name | Spanning tree |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.45527026057243347 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C51823790 |
| concepts[10].level | 2 |
| concepts[10].score | 0.43833598494529724 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q504353 |
| concepts[10].display_name | Greedy algorithm |
| concepts[11].id | https://openalex.org/C2778770139 |
| concepts[11].level | 2 |
| concepts[11].score | 0.4229172468185425 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1966904 |
| concepts[11].display_name | Solver |
| concepts[12].id | https://openalex.org/C13743678 |
| concepts[12].level | 2 |
| concepts[12].score | 0.41414502263069153 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q240464 |
| concepts[12].display_name | Minimum spanning tree |
| concepts[13].id | https://openalex.org/C100560664 |
| concepts[13].level | 4 |
| concepts[13].score | 0.3487150967121124 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q3608019 |
| concepts[13].display_name | K-ary tree |
| concepts[14].id | https://openalex.org/C126255220 |
| concepts[14].level | 1 |
| concepts[14].score | 0.31991201639175415 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[14].display_name | Mathematical optimization |
| concepts[15].id | https://openalex.org/C163797641 |
| concepts[15].level | 3 |
| concepts[15].score | 0.26039278507232666 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q2067937 |
| concepts[15].display_name | Tree structure |
| concepts[16].id | https://openalex.org/C197855036 |
| concepts[16].level | 2 |
| concepts[16].score | 0.09028357267379761 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q380172 |
| concepts[16].display_name | Binary tree |
| concepts[17].id | https://openalex.org/C134306372 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[17].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/steiner-tree-problem |
| keywords[0].score | 0.9160599708557129 |
| keywords[0].display_name | Steiner tree problem |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.6985397338867188 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/approximation-algorithm |
| keywords[2].score | 0.697677731513977 |
| keywords[2].display_name | Approximation algorithm |
| keywords[3].id | https://openalex.org/keywords/mathematics |
| keywords[3].score | 0.6701760292053223 |
| keywords[3].display_name | Mathematics |
| keywords[4].id | https://openalex.org/keywords/generalization |
| keywords[4].score | 0.5517899990081787 |
| keywords[4].display_name | Generalization |
| keywords[5].id | https://openalex.org/keywords/k-minimum-spanning-tree |
| keywords[5].score | 0.5415838360786438 |
| keywords[5].display_name | k-minimum spanning tree |
| keywords[6].id | https://openalex.org/keywords/gomory–hu-tree |
| keywords[6].score | 0.48628342151641846 |
| keywords[6].display_name | Gomory–Hu tree |
| keywords[7].id | https://openalex.org/keywords/tree |
| keywords[7].score | 0.4763203561306 |
| keywords[7].display_name | Tree (set theory) |
| keywords[8].id | https://openalex.org/keywords/spanning-tree |
| keywords[8].score | 0.45546942949295044 |
| keywords[8].display_name | Spanning tree |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.45527026057243347 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/greedy-algorithm |
| keywords[10].score | 0.43833598494529724 |
| keywords[10].display_name | Greedy algorithm |
| keywords[11].id | https://openalex.org/keywords/solver |
| keywords[11].score | 0.4229172468185425 |
| keywords[11].display_name | Solver |
| keywords[12].id | https://openalex.org/keywords/minimum-spanning-tree |
| keywords[12].score | 0.41414502263069153 |
| keywords[12].display_name | Minimum spanning tree |
| keywords[13].id | https://openalex.org/keywords/k-ary-tree |
| keywords[13].score | 0.3487150967121124 |
| keywords[13].display_name | K-ary tree |
| keywords[14].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[14].score | 0.31991201639175415 |
| keywords[14].display_name | Mathematical optimization |
| keywords[15].id | https://openalex.org/keywords/tree-structure |
| keywords[15].score | 0.26039278507232666 |
| keywords[15].display_name | Tree structure |
| keywords[16].id | https://openalex.org/keywords/binary-tree |
| keywords[16].score | 0.09028357267379761 |
| keywords[16].display_name | Binary tree |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:12870 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4 |
| locations[1].id | mag:3082850793 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | arXiv (Cornell University) |
| locations[1].landing_page_url | https://arxiv.org/pdf/2002.06421 |
| locations[2].id | doi:10.4230/lipics.esa.2020.4 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S7407052059 |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | Dagstuhl Research Online Publication Server |
| locations[2].source.host_organization | |
| locations[2].source.host_organization_name | |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.4230/lipics.esa.2020.4 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5001115259 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-6830-9053 |
| authorships[0].author.display_name | Reyan Ahmed |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[0].affiliations[0].raw_affiliation_string | University of Arizona |
| authorships[0].institutions[0].id | https://openalex.org/I138006243 |
| authorships[0].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | University of Arizona |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Reyan Ahmed |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | University of Arizona |
| authorships[1].author.id | https://openalex.org/A5083767818 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-2521-4331 |
| authorships[1].author.display_name | Faryad Darabi Sahneh |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[1].affiliations[0].raw_affiliation_string | University of Arizona |
| authorships[1].institutions[0].id | https://openalex.org/I138006243 |
| authorships[1].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | University of Arizona |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Faryad Darabi Sahneh |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Arizona |
| authorships[2].author.id | https://openalex.org/A5064380948 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-0719-6045 |
| authorships[2].author.display_name | Keaton Hamm |
| authorships[2].countries | US |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I189196454 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Texas at Arlington |
| authorships[2].institutions[0].id | https://openalex.org/I189196454 |
| authorships[2].institutions[0].ror | https://ror.org/019kgqr73 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I189196454 |
| authorships[2].institutions[0].country_code | US |
| authorships[2].institutions[0].display_name | The University of Texas at Arlington |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Keaton Hamm |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | University of Texas at Arlington |
| authorships[3].author.id | https://openalex.org/A5003147292 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-0477-2724 |
| authorships[3].author.display_name | Stephen Kobourov |
| authorships[3].countries | US |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[3].affiliations[0].raw_affiliation_string | University of Arizona, Tucson, United States |
| authorships[3].institutions[0].id | https://openalex.org/I138006243 |
| authorships[3].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[3].institutions[0].country_code | US |
| authorships[3].institutions[0].display_name | University of Arizona |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Stephen Kobourov |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | University of Arizona, Tucson, United States |
| authorships[4].author.id | https://openalex.org/A5088611621 |
| authorships[4].author.orcid | https://orcid.org/0000-0003-4382-466X |
| authorships[4].author.display_name | Richard Spence |
| authorships[4].countries | US |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[4].affiliations[0].raw_affiliation_string | University of Arizona |
| authorships[4].institutions[0].id | https://openalex.org/I138006243 |
| authorships[4].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[4].institutions[0].country_code | US |
| authorships[4].institutions[0].display_name | University of Arizona |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Richard Spence |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | University of Arizona |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11606 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9902999997138977 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2205 |
| primary_topic.subfield.display_name | Civil and Structural Engineering |
| primary_topic.display_name | Infrastructure Maintenance and Monitoring |
| related_works | https://openalex.org/W1519758470, https://openalex.org/W2367195720, https://openalex.org/W1511480398, https://openalex.org/W2030693014, https://openalex.org/W27726302, https://openalex.org/W2943878931, https://openalex.org/W58132005, https://openalex.org/W2100905113, https://openalex.org/W1524393328, https://openalex.org/W1628867809, https://openalex.org/W109985799, https://openalex.org/W1991055327, https://openalex.org/W2963220759, https://openalex.org/W2089847997, https://openalex.org/W2046717228, https://openalex.org/W2513418505, https://openalex.org/W1975290397, https://openalex.org/W2047723482, https://openalex.org/W2012130001, https://openalex.org/W1919263559 |
| cited_by_count | 2 |
| counts_by_year[0].year | 2021 |
| counts_by_year[0].cited_by_count | 2 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:12870 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:12870 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4 |
| publication_date | 2020-01-01 |
| publication_year | 2020 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 114 |
| abstract_inverted_index.T | 18 |
| abstract_inverted_index.a | 7, 34, 77, 124, 139, 160, 173 |
| abstract_inverted_index.c | 100 |
| abstract_inverted_index.n | 105 |
| abstract_inverted_index.v | 49 |
| abstract_inverted_index.In | 27, 168 |
| abstract_inverted_index.We | 0, 195, 222 |
| abstract_inverted_index.an | 135, 201, 224, 231 |
| abstract_inverted_index.as | 206, 208 |
| abstract_inverted_index.at | 204 |
| abstract_inverted_index.by | 118 |
| abstract_inverted_index.et | 120, 157, 210 |
| abstract_inverted_index.in | 14, 111, 129 |
| abstract_inverted_index.is | 73, 94, 106, 134, 149 |
| abstract_inverted_index.it | 246 |
| abstract_inverted_index.n, | 103 |
| abstract_inverted_index.of | 9, 25, 40, 58, 80, 89, 109, 152, 180, 251 |
| abstract_inverted_index.on | 189, 254 |
| abstract_inverted_index.or | 23, 61, 154 |
| abstract_inverted_index.to | 32, 70, 75, 96, 176, 218, 229, 247 |
| abstract_inverted_index.u, | 48 |
| abstract_inverted_index.we | 30, 171 |
| abstract_inverted_index.ρ | 133 |
| abstract_inverted_index.For | 84 |
| abstract_inverted_index.The | 63 |
| abstract_inverted_index.al. | 158 |
| abstract_inverted_index.and | 147, 212, 244, 258 |
| abstract_inverted_index.any | 45 |
| abstract_inverted_index.are | 54, 68 |
| abstract_inverted_index.for | 138, 142, 166, 234 |
| abstract_inverted_index.log | 101, 102 |
| abstract_inverted_index.our | 252 |
| abstract_inverted_index.the | 2, 10, 81, 85, 107, 112, 143, 150, 177, 181, 219, 235, 249 |
| abstract_inverted_index.two | 46 |
| abstract_inverted_index.use | 245 |
| abstract_inverted_index.P(v) | 53 |
| abstract_inverted_index.al., | 121, 211 |
| abstract_inverted_index.both | 255 |
| abstract_inverted_index.case | 64, 88, 179 |
| abstract_inverted_index.cost | 36 |
| abstract_inverted_index.edge | 66, 242 |
| abstract_inverted_index.find | 33 |
| abstract_inverted_index.from | 262 |
| abstract_inverted_index.give | 159 |
| abstract_inverted_index.good | 207 |
| abstract_inverted_index.hard | 95 |
| abstract_inverted_index.more | 86 |
| abstract_inverted_index.rate | 59, 72 |
| abstract_inverted_index.seek | 31 |
| abstract_inverted_index.such | 43 |
| abstract_inverted_index.that | 44, 197 |
| abstract_inverted_index.this | 28, 92, 130, 169, 198 |
| abstract_inverted_index.tree | 5, 12, 37, 145, 162, 185, 193, 238 |
| abstract_inverted_index.with | 50, 98, 164, 216, 240 |
| abstract_inverted_index.𝓁 | 127, 148 |
| abstract_inverted_index.P(u), | 52 |
| abstract_inverted_index.based | 188 |
| abstract_inverted_index.costs | 67, 243 |
| abstract_inverted_index.edges | 39, 57 |
| abstract_inverted_index.exact | 232 |
| abstract_inverted_index.least | 205 |
| abstract_inverted_index.prove | 196 |
| abstract_inverted_index.rates | 42 |
| abstract_inverted_index.ratio | 99, 137, 203 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.their | 71 |
| abstract_inverted_index.using | 56 |
| abstract_inverted_index.where | 16, 65, 104, 132 |
| abstract_inverted_index.(Byrka | 156 |
| abstract_inverted_index.better | 215 |
| abstract_inverted_index.costs, | 91 |
| abstract_inverted_index.factor | 79 |
| abstract_inverted_index.graph. | 113 |
| abstract_inverted_index.graphs | 15, 257 |
| abstract_inverted_index.greedy | 116 |
| abstract_inverted_index.level, | 22 |
| abstract_inverted_index.levels | 155 |
| abstract_inverted_index.linear | 226 |
| abstract_inverted_index.number | 108, 151 |
| abstract_inverted_index.paper, | 170 |
| abstract_inverted_index.random | 256 |
| abstract_inverted_index.simple | 115 |
| abstract_inverted_index.solver | 141 |
| abstract_inverted_index.within | 76 |
| abstract_inverted_index.Steiner | 4, 11, 144, 161, 184, 237 |
| abstract_inverted_index.better. | 62 |
| abstract_inverted_index.compute | 230 |
| abstract_inverted_index.derived | 261 |
| abstract_inverted_index.develop | 223 |
| abstract_inverted_index.general | 87 |
| abstract_inverted_index.integer | 225 |
| abstract_inverted_index.minimum | 35, 191 |
| abstract_inverted_index.natural | 174 |
| abstract_inverted_index.optimal | 82 |
| abstract_inverted_index.optimum | 220 |
| abstract_inverted_index.problem | 13, 93, 146, 239 |
| abstract_inverted_index.quality | 24 |
| abstract_inverted_index.require | 19 |
| abstract_inverted_index.respect | 217 |
| abstract_inverted_index.varying | 20, 41 |
| abstract_inverted_index.|T|+1), | 126 |
| abstract_inverted_index.Charikar | 119, 209 |
| abstract_inverted_index.achieves | 200 |
| abstract_inverted_index.constant | 78 |
| abstract_inverted_index.describe | 172 |
| abstract_inverted_index.evaluate | 248 |
| abstract_inverted_index.however, | 122 |
| abstract_inverted_index.min{2(ln | 125 |
| abstract_inverted_index.performs | 214 |
| abstract_inverted_index.problem, | 29 |
| abstract_inverted_index.problem: | 6 |
| abstract_inverted_index.provides | 123 |
| abstract_inverted_index.service. | 26 |
| abstract_inverted_index.setting, | 131 |
| abstract_inverted_index.solution | 233 |
| abstract_inverted_index.spanning | 192 |
| abstract_inverted_index.vertices | 110 |
| abstract_inverted_index.SteinLib. | 263 |
| abstract_inverted_index.algorithm | 117, 163, 187, 199, 253 |
| abstract_inverted_index.classical | 182 |
| abstract_inverted_index.connected | 55 |
| abstract_inverted_index.example). | 167 |
| abstract_inverted_index.heuristic | 140 |
| abstract_inverted_index.instances | 260 |
| abstract_inverted_index.priority, | 21 |
| abstract_inverted_index.solution. | 83, 221 |
| abstract_inverted_index.terminals | 17, 47 |
| abstract_inverted_index.algorithm. | 194 |
| abstract_inverted_index.containing | 38 |
| abstract_inverted_index.priorities | 51, 153 |
| abstract_inverted_index.ρ≈1.39, | 165 |
| abstract_inverted_index.Kruskal’s | 190 |
| abstract_inverted_index.approximate | 97 |
| abstract_inverted_index.formulation | 228 |
| abstract_inverted_index.multi-level | 3, 178, 236, 259 |
| abstract_inverted_index.performance | 250 |
| abstract_inverted_index.programming | 227 |
| abstract_inverted_index.approximable | 74 |
| abstract_inverted_index.proportional | 69 |
| abstract_inverted_index.approximation | 136, 186, 202 |
| abstract_inverted_index.(single-level) | 183 |
| abstract_inverted_index.experimentally | 213 |
| abstract_inverted_index.generalization | 8, 175 |
| abstract_inverted_index.min{P(u),P(v)} | 60 |
| abstract_inverted_index.non-proportional | 90, 241 |
| abstract_inverted_index.ρ}-approximation | 128 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 93 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile.value | 0.56404459 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |