Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming Article Swipe
Li-Hsuan Chen
,
Felix Reidl
,
Peter Rossmanith
,
Fernando Sánchez Villaamil
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.3390/a11070098
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.3390/a11070098
Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth d cannot be bounded by (2−ϵ)d·logO(1)n for Vertex Cover, (3−ϵ)d·logO(1)n for 3-Coloring and (3−ϵ)d·logO(1)n for Dominating Set for any ϵ>0. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth d: A pure branching algorithm that runs in time dO(d2)·n and uses space O(d3logd+dlogn) and a hybrid of branching and dynamic programming that achieves a running time of O(3dlogd·n) while using O(2ddlogd+dlogn) space.
Related Topics
Concepts
Treewidth
Bounded function
Dynamic programming
Mathematics
Pathwidth
Discrete mathematics
Branching (polymer chemistry)
Interval graph
Vertex (graph theory)
Algorithm
Combinatorics
Chordal graph
Computer science
Graph
1-planar graph
Line graph
Materials science
Composite material
Mathematical analysis
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.3390/a11070098
- https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133
- OA Status
- gold
- Cited By
- 7
- References
- 36
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2809938360
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2809938360Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.3390/a11070098Digital Object Identifier
- Title
-
Width, Depth, and Space: Tradeoffs between Branching and Dynamic ProgrammingWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-07-01Full publication date if available
- Authors
-
Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez VillaamilList of authors in order
- Landing page
-
https://doi.org/10.3390/a11070098Publisher landing page
- PDF URL
-
https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
goldOpen access status per OpenAlex
- OA URL
-
https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133Direct OA link when available
- Concepts
-
Treewidth, Bounded function, Dynamic programming, Mathematics, Pathwidth, Discrete mathematics, Branching (polymer chemistry), Interval graph, Vertex (graph theory), Algorithm, Combinatorics, Chordal graph, Computer science, Graph, 1-planar graph, Line graph, Materials science, Composite material, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
7Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1, 2023: 1, 2022: 1, 2021: 2, 2020: 1Per-year citation counts (last 5 years)
- References (count)
-
36Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2809938360 |
|---|---|
| doi | https://doi.org/10.3390/a11070098 |
| ids.doi | https://doi.org/10.3390/a11070098 |
| ids.mag | 2809938360 |
| ids.openalex | https://openalex.org/W2809938360 |
| fwci | 0.9910637 |
| type | article |
| title | Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming |
| awards[0].id | https://openalex.org/G3554469531 |
| awards[0].funder_id | https://openalex.org/F4320320879 |
| awards[0].display_name | |
| awards[0].funder_award_id | RO 927/13 |
| awards[0].funder_display_name | Deutsche Forschungsgemeinschaft |
| biblio.issue | 7 |
| biblio.volume | 11 |
| biblio.last_page | 98 |
| biblio.first_page | 98 |
| topics[0].id | https://openalex.org/T10374 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| 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 | Advanced Graph Theory Research |
| 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.9930999875068665 |
| 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/T10996 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9907000064849854 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1704 |
| topics[2].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[2].display_name | Computational Geometry and Mesh Generation |
| funders[0].id | https://openalex.org/F4320320879 |
| funders[0].ror | https://ror.org/018mejw64 |
| funders[0].display_name | Deutsche Forschungsgemeinschaft |
| is_xpac | False |
| apc_list.value | 1400 |
| apc_list.currency | CHF |
| apc_list.value_usd | 1515 |
| apc_paid.value | 1400 |
| apc_paid.currency | CHF |
| apc_paid.value_usd | 1515 |
| concepts[0].id | https://openalex.org/C132569581 |
| concepts[0].level | 5 |
| concepts[0].score | 0.752544641494751 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q5067368 |
| concepts[0].display_name | Treewidth |
| concepts[1].id | https://openalex.org/C34388435 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7305399775505066 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[1].display_name | Bounded function |
| concepts[2].id | https://openalex.org/C37404715 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5801671743392944 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q380679 |
| concepts[2].display_name | Dynamic programming |
| concepts[3].id | https://openalex.org/C33923547 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5542687773704529 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[3].display_name | Mathematics |
| concepts[4].id | https://openalex.org/C43517604 |
| concepts[4].level | 4 |
| concepts[4].score | 0.521999716758728 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q7144893 |
| concepts[4].display_name | Pathwidth |
| concepts[5].id | https://openalex.org/C118615104 |
| concepts[5].level | 1 |
| concepts[5].score | 0.4865664541721344 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[5].display_name | Discrete mathematics |
| concepts[6].id | https://openalex.org/C206175624 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4638718366622925 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q595731 |
| concepts[6].display_name | Branching (polymer chemistry) |
| concepts[7].id | https://openalex.org/C67810366 |
| concepts[7].level | 5 |
| concepts[7].score | 0.4242500960826874 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q835942 |
| concepts[7].display_name | Interval graph |
| concepts[8].id | https://openalex.org/C80899671 |
| concepts[8].level | 3 |
| concepts[8].score | 0.4195629358291626 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[8].display_name | Vertex (graph theory) |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.4181898236274719 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C114614502 |
| concepts[10].level | 1 |
| concepts[10].score | 0.40853965282440186 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[10].display_name | Combinatorics |
| concepts[11].id | https://openalex.org/C160446614 |
| concepts[11].level | 3 |
| concepts[11].score | 0.38607966899871826 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1322892 |
| concepts[11].display_name | Chordal graph |
| concepts[12].id | https://openalex.org/C41008148 |
| concepts[12].level | 0 |
| concepts[12].score | 0.3764583468437195 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[12].display_name | Computer science |
| concepts[13].id | https://openalex.org/C132525143 |
| concepts[13].level | 2 |
| concepts[13].score | 0.35943418741226196 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[13].display_name | Graph |
| concepts[14].id | https://openalex.org/C102192266 |
| concepts[14].level | 4 |
| concepts[14].score | 0.2780161499977112 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q4545823 |
| concepts[14].display_name | 1-planar graph |
| concepts[15].id | https://openalex.org/C203776342 |
| concepts[15].level | 3 |
| concepts[15].score | 0.13611799478530884 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q1378376 |
| concepts[15].display_name | Line graph |
| concepts[16].id | https://openalex.org/C192562407 |
| concepts[16].level | 0 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q228736 |
| concepts[16].display_name | Materials science |
| concepts[17].id | https://openalex.org/C159985019 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q181790 |
| concepts[17].display_name | Composite material |
| concepts[18].id | https://openalex.org/C134306372 |
| concepts[18].level | 1 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[18].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/treewidth |
| keywords[0].score | 0.752544641494751 |
| keywords[0].display_name | Treewidth |
| keywords[1].id | https://openalex.org/keywords/bounded-function |
| keywords[1].score | 0.7305399775505066 |
| keywords[1].display_name | Bounded function |
| keywords[2].id | https://openalex.org/keywords/dynamic-programming |
| keywords[2].score | 0.5801671743392944 |
| keywords[2].display_name | Dynamic programming |
| keywords[3].id | https://openalex.org/keywords/mathematics |
| keywords[3].score | 0.5542687773704529 |
| keywords[3].display_name | Mathematics |
| keywords[4].id | https://openalex.org/keywords/pathwidth |
| keywords[4].score | 0.521999716758728 |
| keywords[4].display_name | Pathwidth |
| keywords[5].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[5].score | 0.4865664541721344 |
| keywords[5].display_name | Discrete mathematics |
| keywords[6].id | https://openalex.org/keywords/branching |
| keywords[6].score | 0.4638718366622925 |
| keywords[6].display_name | Branching (polymer chemistry) |
| keywords[7].id | https://openalex.org/keywords/interval-graph |
| keywords[7].score | 0.4242500960826874 |
| keywords[7].display_name | Interval graph |
| keywords[8].id | https://openalex.org/keywords/vertex |
| keywords[8].score | 0.4195629358291626 |
| keywords[8].display_name | Vertex (graph theory) |
| keywords[9].id | https://openalex.org/keywords/algorithm |
| keywords[9].score | 0.4181898236274719 |
| keywords[9].display_name | Algorithm |
| keywords[10].id | https://openalex.org/keywords/combinatorics |
| keywords[10].score | 0.40853965282440186 |
| keywords[10].display_name | Combinatorics |
| keywords[11].id | https://openalex.org/keywords/chordal-graph |
| keywords[11].score | 0.38607966899871826 |
| keywords[11].display_name | Chordal graph |
| keywords[12].id | https://openalex.org/keywords/computer-science |
| keywords[12].score | 0.3764583468437195 |
| keywords[12].display_name | Computer science |
| keywords[13].id | https://openalex.org/keywords/graph |
| keywords[13].score | 0.35943418741226196 |
| keywords[13].display_name | Graph |
| keywords[14].id | https://openalex.org/keywords/1-planar-graph |
| keywords[14].score | 0.2780161499977112 |
| keywords[14].display_name | 1-planar graph |
| keywords[15].id | https://openalex.org/keywords/line-graph |
| keywords[15].score | 0.13611799478530884 |
| keywords[15].display_name | Line graph |
| language | en |
| locations[0].id | doi:10.3390/a11070098 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S190629608 |
| locations[0].source.issn | 1999-4893 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1999-4893 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | True |
| locations[0].source.display_name | Algorithms |
| locations[0].source.host_organization | https://openalex.org/P4310310987 |
| locations[0].source.host_organization_name | Multidisciplinary Digital Publishing Institute |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310310987 |
| locations[0].source.host_organization_lineage_names | Multidisciplinary Digital Publishing Institute |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133 |
| 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 | Algorithms |
| locations[0].landing_page_url | https://doi.org/10.3390/a11070098 |
| locations[1].id | pmh:oai:doaj.org/article:ce1ae04b7b8b42f280bc2e8803604ad7 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306401280 |
| 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 | DOAJ (DOAJ: Directory of Open Access Journals) |
| locations[1].source.host_organization | |
| locations[1].source.host_organization_name | |
| locations[1].license | cc-by-sa |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by-sa |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | Algorithms, Vol 11, Iss 7, p 98 (2018) |
| locations[1].landing_page_url | https://doaj.org/article/ce1ae04b7b8b42f280bc2e8803604ad7 |
| locations[2].id | pmh:oai:mdpi.com:/1999-4893/11/7/98/ |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400947 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | MDPI (MDPI AG) |
| locations[2].source.host_organization | https://openalex.org/I4210097602 |
| locations[2].source.host_organization_name | Multidisciplinary Digital Publishing Institute (Switzerland) |
| locations[2].source.host_organization_lineage | https://openalex.org/I4210097602 |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | submittedVersion |
| locations[2].raw_type | Text |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | Algorithms |
| locations[2].landing_page_url | http://dx.doi.org/10.3390/a11070098 |
| indexed_in | crossref, doaj |
| authorships[0].author.id | https://openalex.org/A5055424928 |
| authorships[0].author.orcid | https://orcid.org/0009-0007-6528-7064 |
| authorships[0].author.display_name | Li-Hsuan Chen |
| authorships[0].affiliations[0].raw_affiliation_string | AROBOT Innovation, Taiwan |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Li-Hsuan Chen |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | AROBOT Innovation, Taiwan |
| authorships[1].author.id | https://openalex.org/A5049595624 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-2354-3003 |
| authorships[1].author.display_name | Felix Reidl |
| authorships[1].countries | GB |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I184558857 |
| authorships[1].affiliations[0].raw_affiliation_string | Royal Holloway, University of London, TW20 0EX, UK |
| authorships[1].institutions[0].id | https://openalex.org/I184558857 |
| authorships[1].institutions[0].ror | https://ror.org/04g2vpn86 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I124357947, https://openalex.org/I184558857 |
| authorships[1].institutions[0].country_code | GB |
| authorships[1].institutions[0].display_name | Royal Holloway University of London |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Felix Reidl |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Royal Holloway, University of London, TW20 0EX, UK |
| authorships[2].author.id | https://openalex.org/A5062653045 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-0177-8028 |
| authorships[2].author.display_name | Peter Rossmanith |
| authorships[2].countries | DE |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I887968799 |
| authorships[2].affiliations[0].raw_affiliation_string | Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany |
| authorships[2].institutions[0].id | https://openalex.org/I887968799 |
| authorships[2].institutions[0].ror | https://ror.org/04xfq0f34 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I887968799 |
| authorships[2].institutions[0].country_code | DE |
| authorships[2].institutions[0].display_name | RWTH Aachen University |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Peter Rossmanith |
| authorships[2].is_corresponding | True |
| authorships[2].raw_affiliation_strings | Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany |
| authorships[3].author.id | https://openalex.org/A5070683396 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Fernando Sánchez Villaamil |
| authorships[3].countries | DE |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I887968799 |
| authorships[3].affiliations[0].raw_affiliation_string | Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany |
| authorships[3].institutions[0].id | https://openalex.org/I887968799 |
| authorships[3].institutions[0].ror | https://ror.org/04xfq0f34 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I887968799 |
| authorships[3].institutions[0].country_code | DE |
| authorships[3].institutions[0].display_name | RWTH Aachen University |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Fernando Sánchez Villaamil |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133 |
| open_access.oa_status | gold |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10374 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| 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 | Advanced Graph Theory Research |
| related_works | https://openalex.org/W1987143101, https://openalex.org/W2963009577, https://openalex.org/W2788975631, https://openalex.org/W2903402681, https://openalex.org/W4387704327, https://openalex.org/W2251679127, https://openalex.org/W1480846237, https://openalex.org/W1544821268, https://openalex.org/W2407722793, https://openalex.org/W1548014395 |
| cited_by_count | 7 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2023 |
| counts_by_year[1].cited_by_count | 1 |
| counts_by_year[2].year | 2022 |
| counts_by_year[2].cited_by_count | 1 |
| counts_by_year[3].year | 2021 |
| counts_by_year[3].cited_by_count | 2 |
| counts_by_year[4].year | 2020 |
| counts_by_year[4].cited_by_count | 1 |
| counts_by_year[5].year | 2019 |
| counts_by_year[5].cited_by_count | 1 |
| locations_count | 3 |
| best_oa_location.id | doi:10.3390/a11070098 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S190629608 |
| best_oa_location.source.issn | 1999-4893 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1999-4893 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | True |
| best_oa_location.source.display_name | Algorithms |
| best_oa_location.source.host_organization | https://openalex.org/P4310310987 |
| best_oa_location.source.host_organization_name | Multidisciplinary Digital Publishing Institute |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310310987 |
| best_oa_location.source.host_organization_lineage_names | Multidisciplinary Digital Publishing Institute |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133 |
| 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 | Algorithms |
| best_oa_location.landing_page_url | https://doi.org/10.3390/a11070098 |
| primary_location.id | doi:10.3390/a11070098 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S190629608 |
| primary_location.source.issn | 1999-4893 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1999-4893 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | True |
| primary_location.source.display_name | Algorithms |
| primary_location.source.host_organization | https://openalex.org/P4310310987 |
| primary_location.source.host_organization_name | Multidisciplinary Digital Publishing Institute |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310310987 |
| primary_location.source.host_organization_lineage_names | Multidisciplinary Digital Publishing Institute |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://www.mdpi.com/1999-4893/11/7/98/pdf?version=1530435133 |
| 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 | Algorithms |
| primary_location.landing_page_url | https://doi.org/10.3390/a11070098 |
| publication_date | 2018-07-01 |
| publication_year | 2018 |
| referenced_works | https://openalex.org/W21297831, https://openalex.org/W2063675347, https://openalex.org/W1510015875, https://openalex.org/W1497202189, https://openalex.org/W2007873061, https://openalex.org/W2039985220, https://openalex.org/W2913683243, https://openalex.org/W4253175698, https://openalex.org/W1960374579, https://openalex.org/W1901935697, https://openalex.org/W2591652165, https://openalex.org/W2951007762, https://openalex.org/W2143406303, https://openalex.org/W1537449969, https://openalex.org/W135876007, https://openalex.org/W1983860528, https://openalex.org/W6674409683, https://openalex.org/W2016056456, https://openalex.org/W2055916047, https://openalex.org/W1579510955, https://openalex.org/W2130407580, https://openalex.org/W2151669659, https://openalex.org/W1984503189, https://openalex.org/W2048586177, https://openalex.org/W2404960361, https://openalex.org/W2527679477, https://openalex.org/W2048068744, https://openalex.org/W2205189132, https://openalex.org/W4213311856, https://openalex.org/W2064710033, https://openalex.org/W2045326192, https://openalex.org/W2067264828, https://openalex.org/W2142055019, https://openalex.org/W2277535896, https://openalex.org/W2783306705, https://openalex.org/W2093949146 |
| referenced_works_count | 36 |
| abstract_inverted_index.A | 143 |
| abstract_inverted_index.a | 2, 10, 47, 99, 157, 166 |
| abstract_inverted_index.d | 65 |
| abstract_inverted_index.On | 40 |
| abstract_inverted_index.We | 116 |
| abstract_inverted_index.be | 67 |
| abstract_inverted_index.by | 69 |
| abstract_inverted_index.d: | 142 |
| abstract_inverted_index.in | 32, 149 |
| abstract_inverted_index.is | 1 |
| abstract_inverted_index.of | 12, 16, 24, 36, 54, 63, 101, 107, 110, 126, 140, 159, 169 |
| abstract_inverted_index.on | 60, 94, 138 |
| abstract_inverted_index.or | 27 |
| abstract_inverted_index.to | 113, 123 |
| abstract_inverted_index.we | 29, 44, 130 |
| abstract_inverted_index.Set | 81, 137 |
| abstract_inverted_index.and | 77, 103, 152, 156, 161 |
| abstract_inverted_index.any | 55, 83 |
| abstract_inverted_index.are | 19, 30 |
| abstract_inverted_index.for | 71, 75, 79, 82, 135 |
| abstract_inverted_index.has | 7 |
| abstract_inverted_index.lot | 100 |
| abstract_inverted_index.the | 33, 41, 51, 87, 108, 124 |
| abstract_inverted_index.two | 132 |
| abstract_inverted_index.This | 85 |
| abstract_inverted_index.more | 20 |
| abstract_inverted_index.pure | 144 |
| abstract_inverted_index.runs | 148 |
| abstract_inverted_index.seen | 9 |
| abstract_inverted_index.show | 45, 118 |
| abstract_inverted_index.than | 22 |
| abstract_inverted_index.that | 50, 90, 119, 147, 164 |
| abstract_inverted_index.then | 117 |
| abstract_inverted_index.this | 37 |
| abstract_inverted_index.time | 150, 168 |
| abstract_inverted_index.uses | 153 |
| abstract_inverted_index.with | 46 |
| abstract_inverted_index.Since | 14 |
| abstract_inverted_index.depth | 64 |
| abstract_inverted_index.graph | 95 |
| abstract_inverted_index.known | 105 |
| abstract_inverted_index.lends | 121 |
| abstract_inverted_index.novel | 48, 133 |
| abstract_inverted_index.side, | 43 |
| abstract_inverted_index.space | 52, 102, 154 |
| abstract_inverted_index.tree- | 26 |
| abstract_inverted_index.using | 172 |
| abstract_inverted_index.which | 6 |
| abstract_inverted_index.while | 171 |
| abstract_inverted_index.width | 4 |
| abstract_inverted_index.Cover, | 73 |
| abstract_inverted_index.Vertex | 72 |
| abstract_inverted_index.cannot | 66 |
| abstract_inverted_index.common | 88 |
| abstract_inverted_index.design | 125, 131 |
| abstract_inverted_index.graphs | 15, 23, 139 |
| abstract_inverted_index.hybrid | 158 |
| abstract_inverted_index.itself | 122 |
| abstract_inverted_index.space. | 174 |
| abstract_inverted_index.bounded | 17, 25, 68 |
| abstract_inverted_index.consume | 98 |
| abstract_inverted_index.dynamic | 57, 91, 162 |
| abstract_inverted_index.measure | 5 |
| abstract_inverted_index.results | 106 |
| abstract_inverted_index.running | 167 |
| abstract_inverted_index.utility | 35 |
| abstract_inverted_index.achieves | 165 |
| abstract_inverted_index.approach | 49 |
| abstract_inverted_index.classes. | 115 |
| abstract_inverted_index.negative | 42 |
| abstract_inverted_index.problems | 111 |
| abstract_inverted_index.recently | 8 |
| abstract_inverted_index.ϵ>0. | 84 |
| abstract_inverted_index.Treedepth | 0 |
| abstract_inverted_index.algorithm | 59, 146 |
| abstract_inverted_index.branching | 127, 145, 160 |
| abstract_inverted_index.dO(d2)·n | 151 |
| abstract_inverted_index.interest. | 13 |
| abstract_inverted_index.intuition | 89 |
| abstract_inverted_index.treedepth | 18, 61, 120, 141 |
| abstract_inverted_index.3-Coloring | 76 |
| abstract_inverted_index.Dominating | 80, 136 |
| abstract_inverted_index.additional | 38 |
| abstract_inverted_index.algorithms | 93, 134 |
| abstract_inverted_index.formalizes | 86 |
| abstract_inverted_index.interested | 31 |
| abstract_inverted_index.pathwidth, | 28 |
| abstract_inverted_index.restricted | 21, 112 |
| abstract_inverted_index.resurgence | 11 |
| abstract_inverted_index.structure. | 39 |
| abstract_inverted_index.algorithmic | 34 |
| abstract_inverted_index.algorithms. | 128 |
| abstract_inverted_index.complements | 104 |
| abstract_inverted_index.consumption | 53 |
| abstract_inverted_index.necessarily | 97 |
| abstract_inverted_index.programming | 58, 92, 163 |
| abstract_inverted_index.O(3dlogd·n) | 170 |
| abstract_inverted_index.(single-pass) | 56 |
| abstract_inverted_index.Specifically, | 129 |
| abstract_inverted_index.low-treewidth | 114 |
| abstract_inverted_index.decompositions | 62, 96 |
| abstract_inverted_index.O(d3logd+dlogn) | 155 |
| abstract_inverted_index.time-complexity | 109 |
| abstract_inverted_index.O(2ddlogd+dlogn) | 173 |
| abstract_inverted_index.well-established | 3 |
| abstract_inverted_index.(2−ϵ)d·logO(1)n | 70 |
| abstract_inverted_index.(3−ϵ)d·logO(1)n | 74, 78 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 89 |
| corresponding_author_ids | https://openalex.org/A5062653045 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 4 |
| corresponding_institution_ids | https://openalex.org/I887968799 |
| citation_normalized_percentile.value | 0.75843055 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |