Advice complexity of adaptive priority algorithms Article Swipe
Joan Boyar
,
Kim S. Larsen
,
Denis Pankratov
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2023.114318
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2023.114318
The priority model was introduced to capture “greedy-like” algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1016/j.tcs.2023.114318
- OA Status
- hybrid
- Cited By
- 1
- References
- 66
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2977477903
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2977477903Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1016/j.tcs.2023.114318Digital Object Identifier
- Title
-
Advice complexity of adaptive priority algorithmsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-11-22Full publication date if available
- Authors
-
Joan Boyar, Kim S. Larsen, Denis PankratovList of authors in order
- Landing page
-
https://doi.org/10.1016/j.tcs.2023.114318Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
hybridOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.1016/j.tcs.2023.114318Direct OA link when available
- Concepts
-
Advice (programming), Computer science, Algorithm, Theoretical computer science, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1Per-year citation counts (last 5 years)
- References (count)
-
66Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2977477903 |
|---|---|
| doi | https://doi.org/10.1016/j.tcs.2023.114318 |
| ids.doi | https://doi.org/10.1016/j.tcs.2023.114318 |
| ids.mag | 2977477903 |
| ids.openalex | https://openalex.org/W2977477903 |
| fwci | 0.43955229 |
| type | article |
| title | Advice complexity of adaptive priority algorithms |
| awards[0].id | https://openalex.org/G7234673648 |
| awards[0].funder_id | https://openalex.org/F4320338218 |
| awards[0].display_name | |
| awards[0].funder_award_id | DFF-0135-00018B |
| awards[0].funder_display_name | Exploratory Research Center on Life and Living Systems, National Institutes of Natural Sciences |
| awards[1].id | https://openalex.org/G2533613479 |
| awards[1].funder_id | https://openalex.org/F4320338218 |
| awards[1].display_name | |
| awards[1].funder_award_id | DFF-7014-00041 |
| awards[1].funder_display_name | Exploratory Research Center on Life and Living Systems, National Institutes of Natural Sciences |
| biblio.issue | |
| biblio.volume | 984 |
| biblio.last_page | 114318 |
| biblio.first_page | 114318 |
| topics[0].id | https://openalex.org/T12288 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998999834060669 |
| 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 | Optimization and Search Problems |
| 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.9997000098228455 |
| 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/T10374 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9948999881744385 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Advanced Graph Theory Research |
| funders[0].id | https://openalex.org/F4320322928 |
| funders[0].ror | https://ror.org/02sptwz63 |
| funders[0].display_name | Danmarks Frie Forskningsfond |
| funders[1].id | https://openalex.org/F4320327387 |
| funders[1].ror | |
| funders[1].display_name | Danmarks Frie Forskningsfond |
| funders[2].id | https://openalex.org/F4320334593 |
| funders[2].ror | https://ror.org/01h531d29 |
| funders[2].display_name | Natural Sciences and Engineering Research Council of Canada |
| funders[3].id | https://openalex.org/F4320338218 |
| funders[3].ror | |
| funders[3].display_name | Exploratory Research Center on Life and Living Systems, National Institutes of Natural Sciences |
| is_xpac | False |
| apc_list.value | 2690 |
| apc_list.currency | USD |
| apc_list.value_usd | 2690 |
| apc_paid.value | 2690 |
| apc_paid.currency | USD |
| apc_paid.value_usd | 2690 |
| concepts[0].id | https://openalex.org/C2779955035 |
| concepts[0].level | 2 |
| concepts[0].score | 0.587018609046936 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q4686785 |
| concepts[0].display_name | Advice (programming) |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5434345602989197 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C11413529 |
| concepts[2].level | 1 |
| concepts[2].score | 0.49601706862449646 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[2].display_name | Algorithm |
| concepts[3].id | https://openalex.org/C80444323 |
| concepts[3].level | 1 |
| concepts[3].score | 0.34863951802253723 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[3].display_name | Theoretical computer science |
| concepts[4].id | https://openalex.org/C199360897 |
| concepts[4].level | 1 |
| concepts[4].score | 0.18990427255630493 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[4].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/advice |
| keywords[0].score | 0.587018609046936 |
| keywords[0].display_name | Advice (programming) |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5434345602989197 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/algorithm |
| keywords[2].score | 0.49601706862449646 |
| keywords[2].display_name | Algorithm |
| keywords[3].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[3].score | 0.34863951802253723 |
| keywords[3].display_name | Theoretical computer science |
| keywords[4].id | https://openalex.org/keywords/programming-language |
| keywords[4].score | 0.18990427255630493 |
| keywords[4].display_name | Programming language |
| language | en |
| locations[0].id | doi:10.1016/j.tcs.2023.114318 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S90727058 |
| locations[0].source.issn | 0304-3975, 1879-2294 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 0304-3975 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Theoretical Computer Science |
| locations[0].source.host_organization | https://openalex.org/P4310320990 |
| locations[0].source.host_organization_name | Elsevier BV |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320990 |
| locations[0].source.host_organization_lineage_names | Elsevier BV |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| 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 | Theoretical Computer Science |
| locations[0].landing_page_url | https://doi.org/10.1016/j.tcs.2023.114318 |
| locations[1].id | pmh:oai:sdu.dk:openaire/c98abb13-5c58-47cd-954d-4a3f42406a67 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400423 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | University of Southern Denmark Research Portal (University of Southern Denmark) |
| locations[1].source.host_organization | https://openalex.org/I177969490 |
| locations[1].source.host_organization_name | University of Southern Denmark |
| locations[1].source.host_organization_lineage | https://openalex.org/I177969490 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | publishedVersion |
| locations[1].raw_type | info:eu-repo/semantics/publishedVersion |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | True |
| locations[1].is_published | True |
| locations[1].raw_source_name | Boyar, J, Larsen, K S & Pankratov, D 2024, 'Advice complexity of adaptive priority algorithms', Theoretical Computer Science, vol. 984, 114318. https://doi.org/10.1016/j.tcs.2023.114318 |
| locations[1].landing_page_url | https://portal.findresearcher.sdu.dk/da/publications/c98abb13-5c58-47cd-954d-4a3f42406a67 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5068354624 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-0725-8341 |
| authorships[0].author.display_name | Joan Boyar |
| authorships[0].countries | DK |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I177969490 |
| authorships[0].affiliations[0].raw_affiliation_string | Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark |
| authorships[0].institutions[0].id | https://openalex.org/I177969490 |
| authorships[0].institutions[0].ror | https://ror.org/03yrrjy16 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I177969490 |
| authorships[0].institutions[0].country_code | DK |
| authorships[0].institutions[0].display_name | University of Southern Denmark |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Joan Boyar |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark |
| authorships[1].author.id | https://openalex.org/A5000210653 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0560-3794 |
| authorships[1].author.display_name | Kim S. Larsen |
| authorships[1].countries | DK |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I177969490 |
| authorships[1].affiliations[0].raw_affiliation_string | Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark |
| authorships[1].institutions[0].id | https://openalex.org/I177969490 |
| authorships[1].institutions[0].ror | https://ror.org/03yrrjy16 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I177969490 |
| authorships[1].institutions[0].country_code | DK |
| authorships[1].institutions[0].display_name | University of Southern Denmark |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Kim S. Larsen |
| authorships[1].is_corresponding | True |
| authorships[1].raw_affiliation_strings | Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark |
| authorships[2].author.id | https://openalex.org/A5102878447 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6183-8363 |
| authorships[2].author.display_name | Denis Pankratov |
| authorships[2].countries | CA |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I60158472 |
| authorships[2].affiliations[0].raw_affiliation_string | Department of Computer Science and Software Engineering, Concordia University, 2155 Guy St., Montreal, Quebec H3H 2L9, Canada |
| authorships[2].institutions[0].id | https://openalex.org/I60158472 |
| authorships[2].institutions[0].ror | https://ror.org/0420zvk78 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I60158472 |
| authorships[2].institutions[0].country_code | CA |
| authorships[2].institutions[0].display_name | Concordia University |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Denis Pankratov |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Department of Computer Science and Software Engineering, Concordia University, 2155 Guy St., Montreal, Quebec H3H 2L9, Canada |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.1016/j.tcs.2023.114318 |
| open_access.oa_status | hybrid |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Advice complexity of adaptive priority algorithms |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T12288 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998999834060669 |
| 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 | Optimization and Search Problems |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4393601209, https://openalex.org/W4404663548, https://openalex.org/W3090906284, https://openalex.org/W253876680, https://openalex.org/W4393803066, https://openalex.org/W1987931999, https://openalex.org/W4293797372 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | doi:10.1016/j.tcs.2023.114318 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S90727058 |
| best_oa_location.source.issn | 0304-3975, 1879-2294 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 0304-3975 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Theoretical Computer Science |
| best_oa_location.source.host_organization | https://openalex.org/P4310320990 |
| best_oa_location.source.host_organization_name | Elsevier BV |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320990 |
| best_oa_location.source.host_organization_lineage_names | Elsevier BV |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| 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 | Theoretical Computer Science |
| best_oa_location.landing_page_url | https://doi.org/10.1016/j.tcs.2023.114318 |
| primary_location.id | doi:10.1016/j.tcs.2023.114318 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S90727058 |
| primary_location.source.issn | 0304-3975, 1879-2294 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 0304-3975 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Theoretical Computer Science |
| primary_location.source.host_organization | https://openalex.org/P4310320990 |
| primary_location.source.host_organization_name | Elsevier BV |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320990 |
| primary_location.source.host_organization_lineage_names | Elsevier BV |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| 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 | Theoretical Computer Science |
| primary_location.landing_page_url | https://doi.org/10.1016/j.tcs.2023.114318 |
| publication_date | 2023-11-22 |
| publication_year | 2023 |
| referenced_works | https://openalex.org/W2062671967, https://openalex.org/W6632148990, https://openalex.org/W2130407580, https://openalex.org/W2132274124, https://openalex.org/W2056760235, https://openalex.org/W2146319320, https://openalex.org/W2809834751, https://openalex.org/W2040556211, https://openalex.org/W2595319805, https://openalex.org/W6630196273, https://openalex.org/W3136693265, https://openalex.org/W2136026170, https://openalex.org/W2807933378, https://openalex.org/W6724543136, https://openalex.org/W2149370230, https://openalex.org/W1970290925, https://openalex.org/W2062897452, https://openalex.org/W2057361103, https://openalex.org/W3135922541, https://openalex.org/W2112906671, https://openalex.org/W6639167096, https://openalex.org/W6675824466, https://openalex.org/W2109659895, https://openalex.org/W2015963099, https://openalex.org/W2089718638, https://openalex.org/W2038319432, https://openalex.org/W2900579929, https://openalex.org/W2089269509, https://openalex.org/W2094683677, https://openalex.org/W2081254453, https://openalex.org/W1554718677, https://openalex.org/W6759352090, https://openalex.org/W6689995656, https://openalex.org/W6687430776, https://openalex.org/W6631504570, https://openalex.org/W2044326680, https://openalex.org/W6602697920, https://openalex.org/W2130640756, https://openalex.org/W2142044446, https://openalex.org/W6649662083, https://openalex.org/W2091593479, https://openalex.org/W1966674384, https://openalex.org/W1999518031, https://openalex.org/W6685975683, https://openalex.org/W2627898316, https://openalex.org/W1979753555, https://openalex.org/W2003016446, https://openalex.org/W2071232852, https://openalex.org/W4255288880, https://openalex.org/W2159308691, https://openalex.org/W3135932689, https://openalex.org/W1772507020, https://openalex.org/W2014228444, https://openalex.org/W2240416680, https://openalex.org/W2182988742, https://openalex.org/W1689936258, https://openalex.org/W1884349932, https://openalex.org/W2681244209, https://openalex.org/W67184062, https://openalex.org/W2106260425, https://openalex.org/W2962942578, https://openalex.org/W1527517713, https://openalex.org/W2100658172, https://openalex.org/W2507673992, https://openalex.org/W2606892140, https://openalex.org/W2530498857 |
| referenced_works_count | 66 |
| abstract_inverted_index.a | 32, 117, 145 |
| abstract_inverted_index.As | 124 |
| abstract_inverted_index.No | 176 |
| abstract_inverted_index.To | 57 |
| abstract_inverted_index.We | 77, 86, 206 |
| abstract_inverted_index.an | 191 |
| abstract_inverted_index.as | 225 |
| abstract_inverted_index.at | 170 |
| abstract_inverted_index.be | 223 |
| abstract_inverted_index.by | 10, 116 |
| abstract_inverted_index.in | 16, 52, 121, 219, 263 |
| abstract_inverted_index.is | 75 |
| abstract_inverted_index.of | 13, 19, 44, 60, 71, 108, 119, 160, 174, 201, 259 |
| abstract_inverted_index.on | 41, 157, 249, 256 |
| abstract_inverted_index.to | 5, 28, 47, 83, 96, 129, 203 |
| abstract_inverted_index.we | 143, 188 |
| abstract_inverted_index.Our | 164 |
| abstract_inverted_index.The | 0, 217 |
| abstract_inverted_index.all | 112, 227, 232 |
| abstract_inverted_index.and | 31, 110, 138, 168, 187, 212, 231 |
| abstract_inverted_index.are | 64 |
| abstract_inverted_index.can | 182, 222 |
| abstract_inverted_index.for | 37, 153 |
| abstract_inverted_index.the | 11, 17, 22, 42, 61, 67, 79, 88, 92, 99, 106, 122 |
| abstract_inverted_index.two | 120 |
| abstract_inverted_index.was | 3, 26, 35 |
| abstract_inverted_index.area | 18 |
| abstract_inverted_index.bits | 173, 200 |
| abstract_inverted_index.both | 134 |
| abstract_inverted_index.case | 95 |
| abstract_inverted_index.even | 68 |
| abstract_inverted_index.from | 91 |
| abstract_inverted_index.more | 100, 197 |
| abstract_inverted_index.most | 59, 171 |
| abstract_inverted_index.seen | 224 |
| abstract_inverted_index.show | 207 |
| abstract_inverted_index.than | 198 |
| abstract_inverted_index.that | 63, 126, 190, 237 |
| abstract_inverted_index.this | 53, 264 |
| abstract_inverted_index.uses | 169 |
| abstract_inverted_index.way. | 265 |
| abstract_inverted_index.with | 98, 141, 151, 194, 215, 235 |
| abstract_inverted_index.work | 97 |
| abstract_inverted_index.7n/22 | 172, 199 |
| abstract_inverted_index.Cover | 156 |
| abstract_inverted_index.Lower | 247 |
| abstract_inverted_index.exact | 210, 242, 245, 260 |
| abstract_inverted_index.fixed | 23, 93 |
| abstract_inverted_index.imply | 253 |
| abstract_inverted_index.lower | 39, 114, 254 |
| abstract_inverted_index.model | 2, 25, 70, 82 |
| abstract_inverted_index.needs | 196 |
| abstract_inverted_index.proof | 107 |
| abstract_inverted_index.prove | 189 |
| abstract_inverted_index.reach | 204 |
| abstract_inverted_index.times | 258 |
| abstract_inverted_index.Vertex | 155 |
| abstract_inverted_index.adding | 127 |
| abstract_inverted_index.advice | 14, 45, 128, 152, 181, 195, 202, 229, 236 |
| abstract_inverted_index.amount | 43 |
| abstract_inverted_index.bounds | 40, 115, 248, 255 |
| abstract_inverted_index.define | 240 |
| abstract_inverted_index.degree | 162 |
| abstract_inverted_index.extend | 78 |
| abstract_inverted_index.factor | 118 |
| abstract_inverted_index.graphs | 159 |
| abstract_inverted_index.model. | 56 |
| abstract_inverted_index.modify | 87 |
| abstract_inverted_index.online | 20, 139, 192 |
| abstract_inverted_index.purely | 146 |
| abstract_inverted_index.rather | 54 |
| abstract_inverted_index.ratios | 51 |
| abstract_inverted_index.three. | 163 |
| abstract_inverted_index.trying | 226 |
| abstract_inverted_index.Minimum | 154 |
| abstract_inverted_index.achieve | 48, 183, 238 |
| abstract_inverted_index.advice, | 30, 142, 186 |
| abstract_inverted_index.advice. | 85, 175, 216 |
| abstract_inverted_index.between | 209 |
| abstract_inverted_index.capture | 6, 58 |
| abstract_inverted_index.certain | 49 |
| abstract_inverted_index.extends | 133 |
| abstract_inverted_index.include | 29, 84 |
| abstract_inverted_index.maximum | 161 |
| abstract_inverted_index.needed. | 76 |
| abstract_inverted_index.present | 144 |
| abstract_inverted_index.proving | 38 |
| abstract_inverted_index.running | 257 |
| abstract_inverted_index.success | 12 |
| abstract_inverted_index.without | 180, 185 |
| abstract_inverted_index.achieves | 166 |
| abstract_inverted_index.adaptive | 72, 80, 102, 130, 135, 148, 177, 251 |
| abstract_inverted_index.designed | 262 |
| abstract_inverted_index.evidence | 125 |
| abstract_inverted_index.extended | 27 |
| abstract_inverted_index.possible | 228 |
| abstract_inverted_index.powerful | 55, 101 |
| abstract_inverted_index.previous | 113 |
| abstract_inverted_index.priority | 1, 24, 73, 81, 94, 103, 131, 136, 149, 178, 213, 233, 244 |
| abstract_inverted_index.process. | 123 |
| abstract_inverted_index.required | 46 |
| abstract_inverted_index.strings, | 230 |
| abstract_inverted_index.stronger | 69 |
| abstract_inverted_index.Motivated | 9 |
| abstract_inverted_index.algorithm | 150, 165, 179, 193 |
| abstract_inverted_index.branching | 218 |
| abstract_inverted_index.developed | 36 |
| abstract_inverted_index.framework | 34, 90 |
| abstract_inverted_index.algorithms | 62, 74, 132, 137, 140, 211, 214, 221, 234, 252, 261 |
| abstract_inverted_index.complexity | 15 |
| abstract_inverted_index.considered | 65 |
| abstract_inverted_index.introduced | 4 |
| abstract_inverted_index.optimality | 167, 184, 239 |
| abstract_inverted_index.algorithms, | 21, 104, 243 |
| abstract_inverted_index.algorithms. | 8, 246 |
| abstract_inverted_index.connections | 208 |
| abstract_inverted_index.correctness | 109 |
| abstract_inverted_index.optimality. | 205 |
| abstract_inverted_index.simplifying | 105 |
| abstract_inverted_index.advice-based | 250 |
| abstract_inverted_index.greedy-like, | 66 |
| abstract_inverted_index.approximation | 50 |
| abstract_inverted_index.combinatorial | 147 |
| abstract_inverted_index.corresponding | 241 |
| abstract_inverted_index.strengthening | 111 |
| abstract_inverted_index.triangle-free | 158 |
| abstract_inverted_index.reduction-based | 33, 89 |
| abstract_inverted_index.branch-and-reduce | 220 |
| abstract_inverted_index.“greedy-like” | 7 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 91 |
| corresponding_author_ids | https://openalex.org/A5000210653 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 3 |
| corresponding_institution_ids | https://openalex.org/I177969490 |
| citation_normalized_percentile.value | 0.46147302 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |