A Streaming Algorithm for the Undirected Longest Path Problem Article Swipe
Lasse Kliemann
,
Christian Schielke
,
Anand Srivastav
·
YOU?
·
· 2016
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2016.56
YOU?
·
· 2016
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2016.56
We present the first streaming algorithm for the longest path problem in undirected graphs. The input graph is given as a stream of edges and RAM is limited to only a linear number of edges at a time (linear in the number of vertices n). We prove a per-edge processing time of O(n), where a naive solution would have required Omega(n^2). Moreover, we give a concrete linear upper bound on the number of bits of RAM that are required. On a set of graphs with various structure, we experimentally compare our algorithm with three leading RAM algorithms: Warnsdorf (1823), Pohl-Warnsdorf (1967), and Pongrasz (2012). Although conducting only a small constant number of passes over the input, our algorithm delivers competitive results: with the exception of preferential attachment graphs, we deliver at least 71% of the solution of the best RAM algorithm. The same minimum relative performance of 71% is observed over all graph classes after removing the 10% worst cases. This comparison has strong meaning, since for each instance class there is one algorithm that on average delivers at least 84% of a Hamilton path. In some cases we deliver even better results than any of the RAM algorithms.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.56
- OA Status
- green
- Cited By
- 4
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2535298630
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2535298630Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.esa.2016.56Digital Object Identifier
- Title
-
A Streaming Algorithm for the Undirected Longest Path ProblemWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2016Year of publication
- Publication date
-
2016-01-01Full publication date if available
- Authors
-
Lasse Kliemann, Christian Schielke, Anand SrivastavList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.56Publisher 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.2016.56Direct OA link when available
- Concepts
-
Computer science, Streaming algorithm, Algorithm, Combinatorics, Undirected graph, Path (computing), Time complexity, Graph, Upper and lower bounds, Running time, Binary logarithm, Mathematics, Discrete mathematics, Programming language, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
4Total citation count in OpenAlex
- Citations by year (recent)
-
2022: 2, 2021: 1, 2018: 1Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2535298630 |
|---|---|
| doi | https://doi.org/10.4230/lipics.esa.2016.56 |
| ids.doi | https://doi.org/10.4230/lipics.itcs.2020.39 |
| ids.mag | 2535298630 |
| ids.openalex | https://openalex.org/W2535298630 |
| fwci | 0.29853518 |
| type | article |
| title | A Streaming Algorithm for the Undirected Longest Path Problem |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11478 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9958000183105469 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Caching and Content Delivery |
| 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.9940000176429749 |
| 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/T12288 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9861000180244446 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Optimization and Search Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.551801323890686 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C187166803 |
| concepts[1].level | 3 |
| concepts[1].score | 0.5432156324386597 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2835831 |
| concepts[1].display_name | Streaming algorithm |
| concepts[2].id | https://openalex.org/C11413529 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5280438661575317 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[2].display_name | Algorithm |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.523099422454834 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C3018234147 |
| concepts[4].level | 3 |
| concepts[4].score | 0.5224612951278687 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[4].display_name | Undirected graph |
| concepts[5].id | https://openalex.org/C2777735758 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5013816356658936 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q817765 |
| concepts[5].display_name | Path (computing) |
| concepts[6].id | https://openalex.org/C311688 |
| concepts[6].level | 2 |
| concepts[6].score | 0.49551355838775635 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[6].display_name | Time complexity |
| concepts[7].id | https://openalex.org/C132525143 |
| concepts[7].level | 2 |
| concepts[7].score | 0.49329179525375366 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[7].display_name | Graph |
| concepts[8].id | https://openalex.org/C77553402 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4881008565425873 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[8].display_name | Upper and lower bounds |
| concepts[9].id | https://openalex.org/C3017489831 |
| concepts[9].level | 2 |
| concepts[9].score | 0.45720842480659485 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[9].display_name | Running time |
| concepts[10].id | https://openalex.org/C63553672 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4112411141395569 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q581168 |
| concepts[10].display_name | Binary logarithm |
| concepts[11].id | https://openalex.org/C33923547 |
| concepts[11].level | 0 |
| concepts[11].score | 0.4074261784553528 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[11].display_name | Mathematics |
| concepts[12].id | https://openalex.org/C118615104 |
| concepts[12].level | 1 |
| concepts[12].score | 0.3660152554512024 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[12].display_name | Discrete mathematics |
| concepts[13].id | https://openalex.org/C199360897 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[13].display_name | Programming language |
| concepts[14].id | https://openalex.org/C134306372 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[14].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.551801323890686 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/streaming-algorithm |
| keywords[1].score | 0.5432156324386597 |
| keywords[1].display_name | Streaming algorithm |
| keywords[2].id | https://openalex.org/keywords/algorithm |
| keywords[2].score | 0.5280438661575317 |
| keywords[2].display_name | Algorithm |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.523099422454834 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/undirected-graph |
| keywords[4].score | 0.5224612951278687 |
| keywords[4].display_name | Undirected graph |
| keywords[5].id | https://openalex.org/keywords/path |
| keywords[5].score | 0.5013816356658936 |
| keywords[5].display_name | Path (computing) |
| keywords[6].id | https://openalex.org/keywords/time-complexity |
| keywords[6].score | 0.49551355838775635 |
| keywords[6].display_name | Time complexity |
| keywords[7].id | https://openalex.org/keywords/graph |
| keywords[7].score | 0.49329179525375366 |
| keywords[7].display_name | Graph |
| keywords[8].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[8].score | 0.4881008565425873 |
| keywords[8].display_name | Upper and lower bounds |
| keywords[9].id | https://openalex.org/keywords/running-time |
| keywords[9].score | 0.45720842480659485 |
| keywords[9].display_name | Running time |
| keywords[10].id | https://openalex.org/keywords/binary-logarithm |
| keywords[10].score | 0.4112411141395569 |
| keywords[10].display_name | Binary logarithm |
| keywords[11].id | https://openalex.org/keywords/mathematics |
| keywords[11].score | 0.4074261784553528 |
| keywords[11].display_name | Mathematics |
| keywords[12].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[12].score | 0.3660152554512024 |
| keywords[12].display_name | Discrete mathematics |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:6398 |
| 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.2016.56 |
| locations[1].id | pmh:oai:arXiv.org:1007.1161 |
| 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 | https://arxiv.org/pdf/1007.1161 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/1007.1161 |
| locations[2].id | doi:10.4230/lipics.esa.2016.56 |
| 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.2016.56 |
| locations[3].id | doi:10.4230/lipics.itcs.2020.39 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S7407052059 |
| locations[3].source.type | repository |
| locations[3].source.is_oa | False |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | Dagstuhl Research Online Publication Server |
| locations[3].source.host_organization | |
| locations[3].source.host_organization_name | |
| locations[3].license | cc-by |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | |
| locations[3].license_id | https://openalex.org/licenses/cc-by |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.4230/lipics.itcs.2020.39 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5028061483 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Lasse Kliemann |
| authorships[0].countries | DE |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I32021983 |
| authorships[0].affiliations[0].raw_affiliation_string | Kiel University, Kiel, Germany |
| authorships[0].institutions[0].id | https://openalex.org/I32021983 |
| authorships[0].institutions[0].ror | https://ror.org/04v76ef78 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I32021983 |
| authorships[0].institutions[0].country_code | DE |
| authorships[0].institutions[0].display_name | Christian-Albrechts-Universität zu Kiel |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Lasse Kliemann |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Kiel University, Kiel, Germany |
| authorships[1].author.id | https://openalex.org/A5040379393 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Christian Schielke |
| authorships[1].countries | DE |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I32021983 |
| authorships[1].affiliations[0].raw_affiliation_string | Kiel University, Kiel, Germany |
| authorships[1].institutions[0].id | https://openalex.org/I32021983 |
| authorships[1].institutions[0].ror | https://ror.org/04v76ef78 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I32021983 |
| authorships[1].institutions[0].country_code | DE |
| authorships[1].institutions[0].display_name | Christian-Albrechts-Universität zu Kiel |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Christian Schielke |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Kiel University, Kiel, Germany |
| authorships[2].author.id | https://openalex.org/A5108463602 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Anand Srivastav |
| authorships[2].countries | DE |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I32021983 |
| authorships[2].affiliations[0].raw_affiliation_string | Kiel University, Kiel, Germany |
| authorships[2].institutions[0].id | https://openalex.org/I32021983 |
| authorships[2].institutions[0].ror | https://ror.org/04v76ef78 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I32021983 |
| authorships[2].institutions[0].country_code | DE |
| authorships[2].institutions[0].display_name | Christian-Albrechts-Universität zu Kiel |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Anand Srivastav |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Kiel University, Kiel, Germany |
| 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.2016.56 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2016-10-28T00:00:00 |
| display_name | A Streaming Algorithm for the Undirected Longest Path Problem |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11478 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9958000183105469 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Caching and Content Delivery |
| related_works | https://openalex.org/W2140226761, https://openalex.org/W3098776817, https://openalex.org/W2149483831, https://openalex.org/W1569643709, https://openalex.org/W2088332251, https://openalex.org/W3137352489, https://openalex.org/W2918100086, https://openalex.org/W1884349932, https://openalex.org/W2944911202, https://openalex.org/W2061208844, https://openalex.org/W2087989168, https://openalex.org/W2886948984, https://openalex.org/W2963618817, https://openalex.org/W2140743794, https://openalex.org/W2031827905, https://openalex.org/W2083795876, https://openalex.org/W2418286382, https://openalex.org/W2937030569, https://openalex.org/W2968883141, https://openalex.org/W2175640098 |
| cited_by_count | 4 |
| counts_by_year[0].year | 2022 |
| counts_by_year[0].cited_by_count | 2 |
| counts_by_year[1].year | 2021 |
| counts_by_year[1].cited_by_count | 1 |
| counts_by_year[2].year | 2018 |
| counts_by_year[2].cited_by_count | 1 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:6398 |
| 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.2016.56 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:6398 |
| 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.2016.56 |
| publication_date | 2016-01-01 |
| publication_year | 2016 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 20, 30, 36, 47, 54, 64, 80, 107, 182 |
| abstract_inverted_index.In | 185 |
| abstract_inverted_index.On | 79 |
| abstract_inverted_index.We | 0, 45 |
| abstract_inverted_index.as | 19 |
| abstract_inverted_index.at | 35, 130, 178 |
| abstract_inverted_index.in | 11, 39 |
| abstract_inverted_index.is | 17, 26, 148, 171 |
| abstract_inverted_index.of | 22, 33, 42, 51, 72, 74, 82, 111, 124, 133, 136, 146, 181, 195 |
| abstract_inverted_index.on | 69, 175 |
| abstract_inverted_index.to | 28 |
| abstract_inverted_index.we | 62, 87, 128, 188 |
| abstract_inverted_index.10% | 157 |
| abstract_inverted_index.71% | 132, 147 |
| abstract_inverted_index.84% | 180 |
| abstract_inverted_index.RAM | 25, 75, 95, 139, 197 |
| abstract_inverted_index.The | 14, 141 |
| abstract_inverted_index.all | 151 |
| abstract_inverted_index.and | 24, 101 |
| abstract_inverted_index.any | 194 |
| abstract_inverted_index.are | 77 |
| abstract_inverted_index.for | 6, 166 |
| abstract_inverted_index.has | 162 |
| abstract_inverted_index.n). | 44 |
| abstract_inverted_index.one | 172 |
| abstract_inverted_index.our | 90, 116 |
| abstract_inverted_index.set | 81 |
| abstract_inverted_index.the | 2, 7, 40, 70, 114, 122, 134, 137, 156, 196 |
| abstract_inverted_index.This | 160 |
| abstract_inverted_index.best | 138 |
| abstract_inverted_index.bits | 73 |
| abstract_inverted_index.each | 167 |
| abstract_inverted_index.even | 190 |
| abstract_inverted_index.give | 63 |
| abstract_inverted_index.have | 58 |
| abstract_inverted_index.only | 29, 106 |
| abstract_inverted_index.over | 113, 150 |
| abstract_inverted_index.path | 9 |
| abstract_inverted_index.same | 142 |
| abstract_inverted_index.some | 186 |
| abstract_inverted_index.than | 193 |
| abstract_inverted_index.that | 76, 174 |
| abstract_inverted_index.time | 37, 50 |
| abstract_inverted_index.with | 84, 92, 121 |
| abstract_inverted_index.O(n), | 52 |
| abstract_inverted_index.after | 154 |
| abstract_inverted_index.bound | 68 |
| abstract_inverted_index.cases | 187 |
| abstract_inverted_index.class | 169 |
| abstract_inverted_index.edges | 23, 34 |
| abstract_inverted_index.first | 3 |
| abstract_inverted_index.given | 18 |
| abstract_inverted_index.graph | 16, 152 |
| abstract_inverted_index.input | 15 |
| abstract_inverted_index.least | 131, 179 |
| abstract_inverted_index.naive | 55 |
| abstract_inverted_index.path. | 184 |
| abstract_inverted_index.prove | 46 |
| abstract_inverted_index.since | 165 |
| abstract_inverted_index.small | 108 |
| abstract_inverted_index.there | 170 |
| abstract_inverted_index.three | 93 |
| abstract_inverted_index.upper | 67 |
| abstract_inverted_index.where | 53 |
| abstract_inverted_index.worst | 158 |
| abstract_inverted_index.would | 57 |
| abstract_inverted_index.better | 191 |
| abstract_inverted_index.cases. | 159 |
| abstract_inverted_index.graphs | 83 |
| abstract_inverted_index.input, | 115 |
| abstract_inverted_index.linear | 31, 66 |
| abstract_inverted_index.number | 32, 41, 71, 110 |
| abstract_inverted_index.passes | 112 |
| abstract_inverted_index.stream | 21 |
| abstract_inverted_index.strong | 163 |
| abstract_inverted_index.(1823), | 98 |
| abstract_inverted_index.(1967), | 100 |
| abstract_inverted_index.(2012). | 103 |
| abstract_inverted_index.(linear | 38 |
| abstract_inverted_index.average | 176 |
| abstract_inverted_index.classes | 153 |
| abstract_inverted_index.compare | 89 |
| abstract_inverted_index.deliver | 129, 189 |
| abstract_inverted_index.graphs, | 127 |
| abstract_inverted_index.graphs. | 13 |
| abstract_inverted_index.leading | 94 |
| abstract_inverted_index.limited | 27 |
| abstract_inverted_index.longest | 8 |
| abstract_inverted_index.minimum | 143 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.problem | 10 |
| abstract_inverted_index.results | 192 |
| abstract_inverted_index.various | 85 |
| abstract_inverted_index.Although | 104 |
| abstract_inverted_index.Hamilton | 183 |
| abstract_inverted_index.Pongrasz | 102 |
| abstract_inverted_index.concrete | 65 |
| abstract_inverted_index.constant | 109 |
| abstract_inverted_index.delivers | 118, 177 |
| abstract_inverted_index.instance | 168 |
| abstract_inverted_index.meaning, | 164 |
| abstract_inverted_index.observed | 149 |
| abstract_inverted_index.per-edge | 48 |
| abstract_inverted_index.relative | 144 |
| abstract_inverted_index.removing | 155 |
| abstract_inverted_index.required | 59 |
| abstract_inverted_index.results: | 120 |
| abstract_inverted_index.solution | 56, 135 |
| abstract_inverted_index.vertices | 43 |
| abstract_inverted_index.Moreover, | 61 |
| abstract_inverted_index.Warnsdorf | 97 |
| abstract_inverted_index.algorithm | 5, 91, 117, 173 |
| abstract_inverted_index.exception | 123 |
| abstract_inverted_index.required. | 78 |
| abstract_inverted_index.streaming | 4 |
| abstract_inverted_index.algorithm. | 140 |
| abstract_inverted_index.attachment | 126 |
| abstract_inverted_index.comparison | 161 |
| abstract_inverted_index.conducting | 105 |
| abstract_inverted_index.processing | 49 |
| abstract_inverted_index.structure, | 86 |
| abstract_inverted_index.undirected | 12 |
| abstract_inverted_index.Omega(n^2). | 60 |
| abstract_inverted_index.algorithms. | 198 |
| abstract_inverted_index.algorithms: | 96 |
| abstract_inverted_index.competitive | 119 |
| abstract_inverted_index.performance | 145 |
| abstract_inverted_index.preferential | 125 |
| abstract_inverted_index.Pohl-Warnsdorf | 99 |
| abstract_inverted_index.experimentally | 88 |
| cited_by_percentile_year.max | 96 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.67120254 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |