A general framework for multi-level subsetwise graph sparsifiers Article Swipe
Reyan Ahmed
,
Keaton Hamm
,
Mohammad Javad Latifi Jebelli
,
Stephen Kobourov
,
Faryad Darabi Sahneh
,
Richard Spence
·
YOU?
·
· 2019
· Open Access
·
YOU?
·
· 2019
· Open Access
·
Given an undirected weighted graph $G(V,E)$, a subsetwise sparsifier over a terminal set $T\subset V$ is a subgraph $G'$ having a certain structure which connects the terminals. Examples are Steiner trees (minimal-weight trees spanning $T$) and subsetwise spanners (subgraphs $G'(V',E')$ such that for given $\alpha,\beta\geq1$, $d_{G'}(u,v)\leq \alpha d_{G}(u,v)+\beta$ for $u,v\in T$). Multi-level subsetwise sparsifiers are generalizations in which terminal vertices require different levels or grades of service. This paper gives a flexible approximation algorithm for several multi-level subsetwise sparsifier problems, including multi-level graph spanners, Steiner trees, and $k$--connected subgraphs. The algorithm relies on computing an approximation to the single level instance of the problem% and an efficient approach to obtain a multi-level solution. For the subsetwise spanner problem, there are few existing approximation algorithms for even a single level; consequently we give a new polynomial time algorithm for computing a subsetwise spanner for a single level. Specifically, we show that for $k\in\N$, $\eps>0$, and $T\subset V$, there is a subsetwise $(2k-1)(1+\eps)$--spanner with total weight $O(|T|^\frac1kW(\ST(G,T)))$, where $W(\ST(G,T))$ is the weight of the Steiner tree of $G$ over the subset $T$. This is the first algorithm and corresponding weight guarantee for a multiplicative subsetwise spanner for nonplanar graphs. We also generalize a result of Klein to give a constant approximation to the multi-level subsetwise spanner problem for planar graphs. Additionally, we give a polynomial-size ILP for optimally computing pairwise spanners of arbitrary distortion (beyond linear distortion functions), and provide experiments to illustrate the performance of our algorithms.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://arxiv.org/abs/1905.00536
- OA Status
- green
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2942597279
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2942597279Canonical identifier for this work in OpenAlex
- Title
-
A general framework for multi-level subsetwise graph sparsifiersWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2019Year of publication
- Publication date
-
2019-05-01Full publication date if available
- Authors
-
Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard SpenceList of authors in order
- Landing page
-
https://arxiv.org/abs/1905.00536Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/abs/1905.00536Direct OA link when available
- Concepts
-
Spanner, Multiplicative function, Steiner tree problem, Combinatorics, Spanning tree, Approximation algorithm, Mathematics, Undirected graph, Graph, Discrete mathematics, Time complexity, Computer science, Mathematical analysis, Distributed computingTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2942597279 |
|---|---|
| doi | |
| ids.mag | 2942597279 |
| ids.openalex | https://openalex.org/W2942597279 |
| fwci | |
| type | preprint |
| title | A general framework for multi-level subsetwise graph sparsifiers |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10720 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9829999804496765 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Complexity and Algorithms in Graphs |
| topics[1].id | https://openalex.org/T10374 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9599999785423279 |
| 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 | Advanced Graph Theory Research |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2779585601 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9424088001251221 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q4049850 |
| concepts[0].display_name | Spanner |
| concepts[1].id | https://openalex.org/C42747912 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7832379341125488 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1048447 |
| concepts[1].display_name | Multiplicative function |
| concepts[2].id | https://openalex.org/C76220878 |
| concepts[2].level | 2 |
| concepts[2].score | 0.7099687457084656 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1764144 |
| concepts[2].display_name | Steiner tree problem |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.6735832691192627 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C64331007 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5961410999298096 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q831672 |
| concepts[4].display_name | Spanning tree |
| concepts[5].id | https://openalex.org/C148764684 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5798514485359192 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[5].display_name | Approximation algorithm |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.572648286819458 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C3018234147 |
| concepts[7].level | 3 |
| concepts[7].score | 0.4594581425189972 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[7].display_name | Undirected graph |
| concepts[8].id | https://openalex.org/C132525143 |
| concepts[8].level | 2 |
| concepts[8].score | 0.45111942291259766 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[8].display_name | Graph |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.4180601239204407 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C311688 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4120698571205139 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[10].display_name | Time complexity |
| concepts[11].id | https://openalex.org/C41008148 |
| concepts[11].level | 0 |
| concepts[11].score | 0.27716872096061707 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[11].display_name | Computer science |
| concepts[12].id | https://openalex.org/C134306372 |
| concepts[12].level | 1 |
| concepts[12].score | 0.05598577857017517 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[12].display_name | Mathematical analysis |
| concepts[13].id | https://openalex.org/C120314980 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q180634 |
| concepts[13].display_name | Distributed computing |
| keywords[0].id | https://openalex.org/keywords/spanner |
| keywords[0].score | 0.9424088001251221 |
| keywords[0].display_name | Spanner |
| keywords[1].id | https://openalex.org/keywords/multiplicative-function |
| keywords[1].score | 0.7832379341125488 |
| keywords[1].display_name | Multiplicative function |
| keywords[2].id | https://openalex.org/keywords/steiner-tree-problem |
| keywords[2].score | 0.7099687457084656 |
| keywords[2].display_name | Steiner tree problem |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.6735832691192627 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/spanning-tree |
| keywords[4].score | 0.5961410999298096 |
| keywords[4].display_name | Spanning tree |
| keywords[5].id | https://openalex.org/keywords/approximation-algorithm |
| keywords[5].score | 0.5798514485359192 |
| keywords[5].display_name | Approximation algorithm |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.572648286819458 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/undirected-graph |
| keywords[7].score | 0.4594581425189972 |
| keywords[7].display_name | Undirected graph |
| keywords[8].id | https://openalex.org/keywords/graph |
| keywords[8].score | 0.45111942291259766 |
| keywords[8].display_name | Graph |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.4180601239204407 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/time-complexity |
| keywords[10].score | 0.4120698571205139 |
| keywords[10].display_name | Time complexity |
| keywords[11].id | https://openalex.org/keywords/computer-science |
| keywords[11].score | 0.27716872096061707 |
| keywords[11].display_name | Computer science |
| keywords[12].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[12].score | 0.05598577857017517 |
| keywords[12].display_name | Mathematical analysis |
| language | en |
| locations[0].id | mag:2942597279 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | arXiv (Cornell University) |
| locations[0].landing_page_url | https://arxiv.org/abs/1905.00536 |
| 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 | Abu Reyan Ahmed |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | University of Arizona |
| authorships[1].author.id | https://openalex.org/A5064380948 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0719-6045 |
| authorships[1].author.display_name | Keaton Hamm |
| 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 | Keaton Hamm |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Arizona |
| authorships[2].author.id | https://openalex.org/A5033797478 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-0088-266X |
| authorships[2].author.display_name | Mohammad Javad Latifi Jebelli |
| authorships[2].countries | US |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Arizona |
| authorships[2].institutions[0].id | https://openalex.org/I138006243 |
| authorships[2].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[2].institutions[0].country_code | US |
| authorships[2].institutions[0].display_name | University of Arizona |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Mohammad Javad Latifi Jebelli |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | University of Arizona |
| 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].author_position | middle |
| authorships[3].raw_author_name | Stephen G. Kobourov |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5083767818 |
| authorships[4].author.orcid | https://orcid.org/0000-0003-2521-4331 |
| authorships[4].author.display_name | Faryad Darabi Sahneh |
| 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 | middle |
| authorships[4].raw_author_name | Faryad Darabi Sahneh |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | University of Arizona |
| authorships[5].author.id | https://openalex.org/A5088611621 |
| authorships[5].author.orcid | https://orcid.org/0000-0003-4382-466X |
| authorships[5].author.display_name | Richard Spence |
| authorships[5].countries | US |
| authorships[5].affiliations[0].institution_ids | https://openalex.org/I138006243 |
| authorships[5].affiliations[0].raw_affiliation_string | University of Arizona |
| authorships[5].institutions[0].id | https://openalex.org/I138006243 |
| authorships[5].institutions[0].ror | https://ror.org/03m2x1q45 |
| authorships[5].institutions[0].type | education |
| authorships[5].institutions[0].lineage | https://openalex.org/I138006243 |
| authorships[5].institutions[0].country_code | US |
| authorships[5].institutions[0].display_name | University of Arizona |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Richard Spence |
| authorships[5].is_corresponding | False |
| authorships[5].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://arxiv.org/abs/1905.00536 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2019-05-09T00:00:00 |
| display_name | A general framework for multi-level subsetwise graph sparsifiers |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-10-10T17:16:08.811792 |
| primary_topic.id | https://openalex.org/T10720 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9829999804496765 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Complexity and Algorithms in Graphs |
| related_works | https://openalex.org/W2057046770, https://openalex.org/W2049095546, https://openalex.org/W1489900072, https://openalex.org/W1678652586, https://openalex.org/W1956345397, https://openalex.org/W2890355536, https://openalex.org/W2963583531, https://openalex.org/W3082434130, https://openalex.org/W2143963903, https://openalex.org/W2577636362, https://openalex.org/W192578035, https://openalex.org/W2103905945, https://openalex.org/W25942946, https://openalex.org/W2950335857, https://openalex.org/W2292508615, https://openalex.org/W2950040818, https://openalex.org/W2950837829, https://openalex.org/W2246992779, https://openalex.org/W2342538925, https://openalex.org/W1863224559 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | mag:2942597279 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| 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 | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | arXiv (Cornell University) |
| best_oa_location.landing_page_url | https://arxiv.org/abs/1905.00536 |
| primary_location.id | mag:2942597279 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | arXiv (Cornell University) |
| primary_location.landing_page_url | https://arxiv.org/abs/1905.00536 |
| publication_date | 2019-05-01 |
| publication_year | 2019 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 6, 10, 16, 20, 70, 110, 126, 132, 139, 143, 158, 190, 200, 206, 221 |
| abstract_inverted_index.V$ | 14 |
| abstract_inverted_index.an | 1, 94, 105 |
| abstract_inverted_index.in | 56 |
| abstract_inverted_index.is | 15, 157, 167, 181 |
| abstract_inverted_index.of | 65, 101, 170, 174, 202, 229, 243 |
| abstract_inverted_index.on | 92 |
| abstract_inverted_index.or | 63 |
| abstract_inverted_index.to | 96, 108, 204, 209, 239 |
| abstract_inverted_index.we | 130, 147, 219 |
| abstract_inverted_index.$G$ | 175 |
| abstract_inverted_index.ILP | 223 |
| abstract_inverted_index.The | 89 |
| abstract_inverted_index.V$, | 155 |
| abstract_inverted_index.and | 35, 86, 104, 153, 185, 236 |
| abstract_inverted_index.are | 28, 54, 119 |
| abstract_inverted_index.few | 120 |
| abstract_inverted_index.for | 42, 48, 74, 124, 137, 142, 150, 189, 194, 215, 224 |
| abstract_inverted_index.new | 133 |
| abstract_inverted_index.our | 244 |
| abstract_inverted_index.set | 12 |
| abstract_inverted_index.the | 25, 97, 102, 114, 168, 171, 177, 182, 210, 241 |
| abstract_inverted_index. We | 197 |
| abstract_inverted_index.$G'$ | 18 |
| abstract_inverted_index.$T$) | 34 |
| abstract_inverted_index.$T$. | 179 |
| abstract_inverted_index.T$). | 50 |
| abstract_inverted_index.This | 180 |
| abstract_inverted_index.also | 198 |
| abstract_inverted_index.even | 125 |
| abstract_inverted_index.give | 131, 205, 220 |
| abstract_inverted_index.over | 9, 176 |
| abstract_inverted_index.show | 148 |
| abstract_inverted_index.such | 40 |
| abstract_inverted_index.that | 41, 149 |
| abstract_inverted_index.time | 135 |
| abstract_inverted_index.tree | 173 |
| abstract_inverted_index.with | 161 |
| abstract_inverted_index. For | 113 |
| abstract_inverted_index.Given | 0 |
| abstract_inverted_index.Klein | 203 |
| abstract_inverted_index.first | 183 |
| abstract_inverted_index.given | 43 |
| abstract_inverted_index.gives | 69 |
| abstract_inverted_index.graph | 4, 82 |
| abstract_inverted_index.level | 99 |
| abstract_inverted_index.paper | 68 |
| abstract_inverted_index.there | 118, 156 |
| abstract_inverted_index.total | 162 |
| abstract_inverted_index.trees | 30, 32 |
| abstract_inverted_index.where | 165 |
| abstract_inverted_index.which | 23, 57 |
| abstract_inverted_index. This | 67 |
| abstract_inverted_index.\alpha | 46 |
| abstract_inverted_index.grades | 64 |
| abstract_inverted_index.having | 19 |
| abstract_inverted_index.level. | 145 |
| abstract_inverted_index.level; | 128 |
| abstract_inverted_index.levels | 62 |
| abstract_inverted_index.linear | 233 |
| abstract_inverted_index.obtain | 109 |
| abstract_inverted_index.planar | 216 |
| abstract_inverted_index.relies | 91 |
| abstract_inverted_index.result | 201 |
| abstract_inverted_index.single | 98, 127, 144 |
| abstract_inverted_index.subset | 178 |
| abstract_inverted_index.trees, | 85 |
| abstract_inverted_index.weight | 163, 169, 187 |
| abstract_inverted_index.$u,v\in | 49 |
| abstract_inverted_index.(beyond | 232 |
| abstract_inverted_index.Steiner | 29, 84, 172 |
| abstract_inverted_index.certain | 21 |
| abstract_inverted_index.graphs. | 196, 217 |
| abstract_inverted_index.problem | 214 |
| abstract_inverted_index.provide | 237 |
| abstract_inverted_index.require | 60 |
| abstract_inverted_index.several | 75 |
| abstract_inverted_index.spanner | 116, 141, 193, 213 |
| abstract_inverted_index.Examples | 27 |
| abstract_inverted_index.approach | 107 |
| abstract_inverted_index.connects | 24 |
| abstract_inverted_index.constant | 207 |
| abstract_inverted_index.existing | 121 |
| abstract_inverted_index.flexible | 71 |
| abstract_inverted_index.instance | 100 |
| abstract_inverted_index.pairwise | 227 |
| abstract_inverted_index.problem% | 103 |
| abstract_inverted_index.problem, | 117 |
| abstract_inverted_index.service. | 66 |
| abstract_inverted_index.spanners | 37, 228 |
| abstract_inverted_index.spanning | 33 |
| abstract_inverted_index.subgraph | 17 |
| abstract_inverted_index.terminal | 11, 58 |
| abstract_inverted_index.vertices | 59 |
| abstract_inverted_index.weighted | 3 |
| abstract_inverted_index.$G(V,E)$, | 5 |
| abstract_inverted_index.$T\subset | 13, 154 |
| abstract_inverted_index.$\eps>0$, | 152 |
| abstract_inverted_index.$k\in\N$, | 151 |
| abstract_inverted_index.algorithm | 73, 90, 136, 184 |
| abstract_inverted_index.arbitrary | 230 |
| abstract_inverted_index.computing | 93, 138, 226 |
| abstract_inverted_index.different | 61 |
| abstract_inverted_index.efficient | 106 |
| abstract_inverted_index.guarantee | 188 |
| abstract_inverted_index.including | 80 |
| abstract_inverted_index.nonplanar | 195 |
| abstract_inverted_index.optimally | 225 |
| abstract_inverted_index.problems, | 79 |
| abstract_inverted_index.solution. | 112 |
| abstract_inverted_index.spanners, | 83 |
| abstract_inverted_index.structure | 22 |
| abstract_inverted_index.(subgraphs | 38 |
| abstract_inverted_index.algorithms | 123 |
| abstract_inverted_index.distortion | 231, 234 |
| abstract_inverted_index.generalize | 199 |
| abstract_inverted_index.illustrate | 240 |
| abstract_inverted_index.polynomial | 134 |
| abstract_inverted_index.sparsifier | 8, 78 |
| abstract_inverted_index.subgraphs. | 88 |
| abstract_inverted_index.subsetwise | 7, 36, 52, 77, 115, 140, 159, 192, 212 |
| abstract_inverted_index.terminals. | 26 |
| abstract_inverted_index.undirected | 2 |
| abstract_inverted_index.$G'(V',E')$ | 39 |
| abstract_inverted_index.Multi-level | 51 |
| abstract_inverted_index.algorithms. | 245 |
| abstract_inverted_index.experiments | 238 |
| abstract_inverted_index.functions), | 235 |
| abstract_inverted_index.multi-level | 76, 81, 111, 211 |
| abstract_inverted_index.performance | 242 |
| abstract_inverted_index.sparsifiers | 53 |
| abstract_inverted_index.consequently | 129 |
| abstract_inverted_index.$W(\ST(G,T))$ | 166 |
| abstract_inverted_index.Additionally, | 218 |
| abstract_inverted_index.Specifically, | 146 |
| abstract_inverted_index.approximation | 72, 95, 122, 208 |
| abstract_inverted_index.corresponding | 186 |
| abstract_inverted_index.$k$--connected | 87 |
| abstract_inverted_index.multiplicative | 191 |
| abstract_inverted_index.(minimal-weight | 31 |
| abstract_inverted_index.generalizations | 55 |
| abstract_inverted_index.polynomial-size | 222 |
| abstract_inverted_index.$d_{G'}(u,v)\leq | 45 |
| abstract_inverted_index.d_{G}(u,v)+\beta$ | 47 |
| abstract_inverted_index.$\alpha,\beta\geq1$, | 44 |
| abstract_inverted_index.$(2k-1)(1+\eps)$--spanner | 160 |
| abstract_inverted_index.$O(|T|^\frac1kW(\ST(G,T)))$, | 164 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile |