Distributed Recoloring of Interval and Chordal Graphs Article Swipe
Nicolás Bousquet
,
Laurent Feuilloley
,
Marc Heinrich
,
Mikaël Rabie
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.opodis.2021.19
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.opodis.2021.19
One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.
Related Topics
Concepts
Chordal graph
Interval graph
Bounded function
Graph coloring
Computer science
Indifference graph
Combinatorics
Pathwidth
Discrete mathematics
Graph
Split graph
Subroutine
Theoretical computer science
Mathematics
1-planar graph
Line graph
Mathematical analysis
Operating system
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.19
- OA Status
- green
- Cited By
- 1
- References
- 2
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3200847509
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3200847509Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.opodis.2021.19Digital Object Identifier
- Title
-
Distributed Recoloring of Interval and Chordal GraphsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-01-01Full publication date if available
- Authors
-
Nicolás Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël RabieList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.19Publisher 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.OPODIS.2021.19Direct OA link when available
- Concepts
-
Chordal graph, Interval graph, Bounded function, Graph coloring, Computer science, Indifference graph, Combinatorics, Pathwidth, Discrete mathematics, Graph, Split graph, Subroutine, Theoretical computer science, Mathematics, 1-planar graph, Line graph, Mathematical analysis, Operating systemTop 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)
-
2Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3200847509 |
|---|---|
| doi | https://doi.org/10.4230/lipics.opodis.2021.19 |
| ids.doi | https://doi.org/10.4230/lipics.opodis.2021.19 |
| ids.mag | 3200847509 |
| ids.openalex | https://openalex.org/W3200847509 |
| fwci | 0.26334776 |
| type | preprint |
| title | Distributed Recoloring of Interval and Chordal Graphs |
| 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.9991999864578247 |
| 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/T10796 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9980000257492065 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Cooperative Communication and Network Coding |
| topics[2].id | https://openalex.org/T10772 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9975000023841858 |
| 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 | Distributed systems and fault tolerance |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C160446614 |
| concepts[0].level | 3 |
| concepts[0].score | 0.7978978157043457 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1322892 |
| concepts[0].display_name | Chordal graph |
| concepts[1].id | https://openalex.org/C67810366 |
| concepts[1].level | 5 |
| concepts[1].score | 0.7688045501708984 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q835942 |
| concepts[1].display_name | Interval graph |
| concepts[2].id | https://openalex.org/C34388435 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6194714903831482 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[2].display_name | Bounded function |
| concepts[3].id | https://openalex.org/C76946457 |
| concepts[3].level | 3 |
| concepts[3].score | 0.586151123046875 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q504843 |
| concepts[3].display_name | Graph coloring |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5580699443817139 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C74133993 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5361798405647278 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3115472 |
| concepts[5].display_name | Indifference graph |
| concepts[6].id | https://openalex.org/C114614502 |
| concepts[6].level | 1 |
| concepts[6].score | 0.5045899152755737 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[6].display_name | Combinatorics |
| concepts[7].id | https://openalex.org/C43517604 |
| concepts[7].level | 4 |
| concepts[7].score | 0.4797131419181824 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q7144893 |
| concepts[7].display_name | Pathwidth |
| concepts[8].id | https://openalex.org/C118615104 |
| concepts[8].level | 1 |
| concepts[8].score | 0.45273134112358093 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[8].display_name | Discrete mathematics |
| concepts[9].id | https://openalex.org/C132525143 |
| concepts[9].level | 2 |
| concepts[9].score | 0.44937965273857117 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[9].display_name | Graph |
| concepts[10].id | https://openalex.org/C8554925 |
| concepts[10].level | 5 |
| concepts[10].score | 0.4411028027534485 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q3893853 |
| concepts[10].display_name | Split graph |
| concepts[11].id | https://openalex.org/C96147967 |
| concepts[11].level | 2 |
| concepts[11].score | 0.4158817231655121 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q190686 |
| concepts[11].display_name | Subroutine |
| concepts[12].id | https://openalex.org/C80444323 |
| concepts[12].level | 1 |
| concepts[12].score | 0.3735238313674927 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[12].display_name | Theoretical computer science |
| concepts[13].id | https://openalex.org/C33923547 |
| concepts[13].level | 0 |
| concepts[13].score | 0.37015512585639954 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[13].display_name | Mathematics |
| concepts[14].id | https://openalex.org/C102192266 |
| concepts[14].level | 4 |
| concepts[14].score | 0.2622016966342926 |
| 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.2323356568813324 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q1378376 |
| concepts[15].display_name | Line graph |
| concepts[16].id | https://openalex.org/C134306372 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[16].display_name | Mathematical analysis |
| concepts[17].id | https://openalex.org/C111919701 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q9135 |
| concepts[17].display_name | Operating system |
| keywords[0].id | https://openalex.org/keywords/chordal-graph |
| keywords[0].score | 0.7978978157043457 |
| keywords[0].display_name | Chordal graph |
| keywords[1].id | https://openalex.org/keywords/interval-graph |
| keywords[1].score | 0.7688045501708984 |
| keywords[1].display_name | Interval graph |
| keywords[2].id | https://openalex.org/keywords/bounded-function |
| keywords[2].score | 0.6194714903831482 |
| keywords[2].display_name | Bounded function |
| keywords[3].id | https://openalex.org/keywords/graph-coloring |
| keywords[3].score | 0.586151123046875 |
| keywords[3].display_name | Graph coloring |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.5580699443817139 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/indifference-graph |
| keywords[5].score | 0.5361798405647278 |
| keywords[5].display_name | Indifference graph |
| keywords[6].id | https://openalex.org/keywords/combinatorics |
| keywords[6].score | 0.5045899152755737 |
| keywords[6].display_name | Combinatorics |
| keywords[7].id | https://openalex.org/keywords/pathwidth |
| keywords[7].score | 0.4797131419181824 |
| keywords[7].display_name | Pathwidth |
| keywords[8].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[8].score | 0.45273134112358093 |
| keywords[8].display_name | Discrete mathematics |
| keywords[9].id | https://openalex.org/keywords/graph |
| keywords[9].score | 0.44937965273857117 |
| keywords[9].display_name | Graph |
| keywords[10].id | https://openalex.org/keywords/split-graph |
| keywords[10].score | 0.4411028027534485 |
| keywords[10].display_name | Split graph |
| keywords[11].id | https://openalex.org/keywords/subroutine |
| keywords[11].score | 0.4158817231655121 |
| keywords[11].display_name | Subroutine |
| keywords[12].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[12].score | 0.3735238313674927 |
| keywords[12].display_name | Theoretical computer science |
| keywords[13].id | https://openalex.org/keywords/mathematics |
| keywords[13].score | 0.37015512585639954 |
| keywords[13].display_name | Mathematics |
| keywords[14].id | https://openalex.org/keywords/1-planar-graph |
| keywords[14].score | 0.2622016966342926 |
| keywords[14].display_name | 1-planar graph |
| keywords[15].id | https://openalex.org/keywords/line-graph |
| keywords[15].score | 0.2323356568813324 |
| keywords[15].display_name | Line graph |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:15794 |
| 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.OPODIS.2021.19 |
| locations[1].id | pmh:oai:arXiv.org:2109.06021 |
| 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/2109.06021 |
| 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/2109.06021 |
| locations[2].id | pmh:oai:HAL:hal-03610449v1 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306402512 |
| locations[2].source.issn | |
| 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 | HAL (Le Centre pour la Communication Scientifique Directe) |
| locations[2].source.host_organization | https://openalex.org/I1294671590 |
| locations[2].source.host_organization_name | Centre National de la Recherche Scientifique |
| locations[2].source.host_organization_lineage | https://openalex.org/I1294671590 |
| locations[2].license | other-oa |
| locations[2].pdf_url | |
| locations[2].version | submittedVersion |
| locations[2].raw_type | Conference papers |
| locations[2].license_id | https://openalex.org/licenses/other-oa |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | 25th International Conference on Principles of Distributed Systems, OPODIS 2021, Dec 2021, Strasbourg, France. ⟨10.4230/LIPIcs.OPODIS.2021.19⟩ |
| locations[2].landing_page_url | https://hal.science/hal-03610449 |
| locations[3].id | doi:10.4230/lipics.opodis.2021.19 |
| 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].source.host_organization_lineage | |
| 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.opodis.2021.19 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5044190443 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-0170-0503 |
| authorships[0].author.display_name | Nicolás Bousquet |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Nicolas Bousquet |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5080881555 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3994-0898 |
| authorships[1].author.display_name | Laurent Feuilloley |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Laurent Feuilloley |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5045226522 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-4546-2359 |
| authorships[2].author.display_name | Marc Heinrich |
| authorships[2].countries | GB |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I130828816 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Leeds |
| authorships[2].institutions[0].id | https://openalex.org/I130828816 |
| authorships[2].institutions[0].ror | https://ror.org/024mrxd33 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I130828816 |
| authorships[2].institutions[0].country_code | GB |
| authorships[2].institutions[0].display_name | University of Leeds |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Marc Heinrich |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | University of Leeds |
| authorships[3].author.id | https://openalex.org/A5038963808 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-6782-7625 |
| authorships[3].author.display_name | Mikaël Rabie |
| authorships[3].countries | FR |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I4210117673 |
| authorships[3].affiliations[0].raw_affiliation_string | Institut de Recherche en Informatique Fondamentale |
| authorships[3].institutions[0].id | https://openalex.org/I4210117673 |
| authorships[3].institutions[0].ror | https://ror.org/02krdtz55 |
| authorships[3].institutions[0].type | facility |
| authorships[3].institutions[0].lineage | https://openalex.org/I1294671590, https://openalex.org/I1294671590, https://openalex.org/I204730241, https://openalex.org/I4210089394, https://openalex.org/I4210117673, https://openalex.org/I4210139971 |
| authorships[3].institutions[0].country_code | FR |
| authorships[3].institutions[0].display_name | Institut de Recherche en Informatique Fondamentale |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Mikaël Rabie |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Institut de Recherche en Informatique Fondamentale |
| 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.OPODIS.2021.19 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Distributed Recoloring of Interval and Chordal Graphs |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| 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.9991999864578247 |
| 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/W2788975631, https://openalex.org/W2963009577, https://openalex.org/W2903402681, https://openalex.org/W1946718366, https://openalex.org/W1681620790, https://openalex.org/W1987143101, https://openalex.org/W2157783000, https://openalex.org/W4298846841, https://openalex.org/W2952658105, https://openalex.org/W2949743119 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:15794 |
| 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.OPODIS.2021.19 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:15794 |
| 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.OPODIS.2021.19 |
| publication_date | 2022-01-01 |
| publication_year | 2022 |
| referenced_works | https://openalex.org/W1980501142, https://openalex.org/W2154189866 |
| referenced_works_count | 2 |
| abstract_inverted_index.a | 53, 67, 135, 143, 150, 159, 170, 207, 257 |
| abstract_inverted_index.In | 107, 169, 217 |
| abstract_inverted_index.an | 43, 145 |
| abstract_inverted_index.as | 66, 73, 138 |
| abstract_inverted_index.be | 177, 246 |
| abstract_inverted_index.do | 82 |
| abstract_inverted_index.if | 228 |
| abstract_inverted_index.in | 8, 17, 20, 32, 102, 120, 248, 290, 297 |
| abstract_inverted_index.is | 13, 41, 137, 211 |
| abstract_inverted_index.it | 74 |
| abstract_inverted_index.n) | 271, 299 |
| abstract_inverted_index.of | 1, 26, 38, 51, 114, 133, 161, 201, 214, 220, 239, 262, 287, 294 |
| abstract_inverted_index.on | 11, 303 |
| abstract_inverted_index.to | 60, 157, 163, 176, 195, 205, 273 |
| abstract_inverted_index.we | 110, 140, 155, 193, 225, 229, 255, 268, 284 |
| abstract_inverted_index.α | 148 |
| abstract_inverted_index.β | 165 |
| abstract_inverted_index.ω | 235 |
| abstract_inverted_index.2ω | 233 |
| abstract_inverted_index.For | 252 |
| abstract_inverted_index.One | 0 |
| abstract_inverted_index.Our | 276 |
| abstract_inverted_index.The | 191 |
| abstract_inverted_index.and | 4, 19, 65, 79, 94, 126, 149, 154, 209, 222, 264, 293 |
| abstract_inverted_index.are | 141 |
| abstract_inverted_index.for | 70, 265, 311 |
| abstract_inverted_index.get | 274, 285 |
| abstract_inverted_index.has | 29, 56, 99 |
| abstract_inverted_index.how | 198 |
| abstract_inverted_index.is: | 197 |
| abstract_inverted_index.new | 54 |
| abstract_inverted_index.not | 83 |
| abstract_inverted_index.the | 2, 24, 36, 112, 131, 173, 180, 212, 218, 237, 240, 249, 312 |
| abstract_inverted_index.too | 95 |
| abstract_inverted_index.two | 33, 47, 116, 121 |
| abstract_inverted_index.use | 308 |
| abstract_inverted_index.α. | 168 |
| abstract_inverted_index.β, | 153 |
| abstract_inverted_index.More | 129 |
| abstract_inverted_index.also | 278 |
| abstract_inverted_index.been | 30, 57, 100 |
| abstract_inverted_index.both | 16, 59 |
| abstract_inverted_index.case | 219 |
| abstract_inverted_index.find | 158 |
| abstract_inverted_index.from | 167 |
| abstract_inverted_index.have | 230 |
| abstract_inverted_index.less | 231 |
| abstract_inverted_index.many | 199 |
| abstract_inverted_index.more | 103 |
| abstract_inverted_index.need | 269 |
| abstract_inverted_index.one. | 275 |
| abstract_inverted_index.real | 85 |
| abstract_inverted_index.same | 313 |
| abstract_inverted_index.size | 238 |
| abstract_inverted_index.than | 232 |
| abstract_inverted_index.that | 40, 76, 307 |
| abstract_inverted_index.this | 27, 108, 215 |
| abstract_inverted_index.very | 87 |
| abstract_inverted_index.want | 156, 194 |
| abstract_inverted_index.well | 88 |
| abstract_inverted_index.what | 210 |
| abstract_inverted_index.will | 245 |
| abstract_inverted_index.with | 186 |
| abstract_inverted_index.ω+2 | 309 |
| abstract_inverted_index.LOCAL | 181 |
| abstract_inverted_index.after | 259 |
| abstract_inverted_index.being | 236 |
| abstract_inverted_index.extra | 243 |
| abstract_inverted_index.found | 178 |
| abstract_inverted_index.given | 48, 142 |
| abstract_inverted_index.graph | 14, 105, 123, 136 |
| abstract_inverted_index.input | 146 |
| abstract_inverted_index.known | 305 |
| abstract_inverted_index.model | 61, 84 |
| abstract_inverted_index.needs | 175 |
| abstract_inverted_index.nodes | 184 |
| abstract_inverted_index.prove | 226 |
| abstract_inverted_index.radio | 62 |
| abstract_inverted_index.reach | 164 |
| abstract_inverted_index.study | 25, 111 |
| abstract_inverted_index.that, | 227 |
| abstract_inverted_index.their | 187 |
| abstract_inverted_index.these | 115 |
| abstract_inverted_index.where | 183 |
| abstract_inverted_index.which | 301 |
| abstract_inverted_index.{are} | 203 |
| abstract_inverted_index.(with, | 89 |
| abstract_inverted_index.First, | 35 |
| abstract_inverted_index.answer | 196 |
| abstract_inverted_index.colors | 244, 310 |
| abstract_inverted_index.direct | 188 |
| abstract_inverted_index.graphs | 78, 81, 289, 296 |
| abstract_inverted_index.length | 213 |
| abstract_inverted_index.model, | 182 |
| abstract_inverted_index.needed | 204, 247 |
| abstract_inverted_index.paper, | 109 |
| abstract_inverted_index.rounds | 200, 261, 272, 292 |
| abstract_inverted_index.strong | 96 |
| abstract_inverted_index.target | 151 |
| abstract_inverted_index.times. | 315 |
| abstract_inverted_index.useful | 68 |
| abstract_inverted_index.within | 179 |
| abstract_inverted_index.Namely, | 283 |
| abstract_inverted_index.O(ωlog | 298 |
| abstract_inverted_index.Second, | 72 |
| abstract_inverted_index.appears | 75 |
| abstract_inverted_index.between | 46 |
| abstract_inverted_index.chordal | 127, 223, 266, 295 |
| abstract_inverted_index.classic | 280 |
| abstract_inverted_index.clique, | 242 |
| abstract_inverted_index.colors, | 234 |
| abstract_inverted_index.general | 21, 77 |
| abstract_inverted_index.graphs, | 224, 254, 267 |
| abstract_inverted_index.graphs. | 22, 128 |
| abstract_inverted_index.improve | 279 |
| abstract_inverted_index.largest | 241 |
| abstract_inverted_index.network | 63 |
| abstract_inverted_index.problem | 28, 37 |
| abstract_inverted_index.produce | 206, 256 |
| abstract_inverted_index.rounds, | 300 |
| abstract_inverted_index.running | 314 |
| abstract_inverted_index.studied | 101 |
| abstract_inverted_index.(instead | 50 |
| abstract_inverted_index.classes, | 124 |
| abstract_inverted_index.classes. | 106 |
| abstract_inverted_index.coloring | 98, 147, 152, 281 |
| abstract_inverted_index.extended | 31 |
| abstract_inverted_index.follows: | 139 |
| abstract_inverted_index.improves | 302 |
| abstract_inverted_index.interval | 125, 221, 253, 288 |
| abstract_inverted_index.network, | 144 |
| abstract_inverted_index.networks | 12, 86 |
| abstract_inverted_index.previous | 304 |
| abstract_inverted_index.problems | 7 |
| abstract_inverted_index.question | 132, 192 |
| abstract_inverted_index.relevant | 122 |
| abstract_inverted_index.schedule | 160, 174, 258 |
| abstract_inverted_index.setting, | 172 |
| abstract_inverted_index.specific | 104 |
| abstract_inverted_index.starting | 166 |
| abstract_inverted_index.updates, | 64 |
| abstract_inverted_index.Recently, | 23 |
| abstract_inverted_index.coloring, | 15 |
| abstract_inverted_index.coloring. | 71 |
| abstract_inverted_index.colorings | 49, 162 |
| abstract_inverted_index.computing | 10, 42, 52 |
| abstract_inverted_index.efficient | 44 |
| abstract_inverted_index.formally, | 130 |
| abstract_inverted_index.neighbors | 189 |
| abstract_inverted_index.schedule, | 208 |
| abstract_inverted_index.schedule? | 216 |
| abstract_inverted_index.O(ωlog*n) | 291 |
| abstract_inverted_index.algorithms | 306 |
| abstract_inverted_index.coloring), | 55 |
| abstract_inverted_index.colorings. | 251 |
| abstract_inverted_index.recoloring | 119, 134 |
| abstract_inverted_index.subroutine | 69 |
| abstract_inverted_index.techniques | 277 |
| abstract_inverted_index.topologies | 93 |
| abstract_inverted_index.worst-case | 92 |
| abstract_inverted_index.algorithmic | 6 |
| abstract_inverted_index.algorithms. | 282 |
| abstract_inverted_index.communicate | 185 |
| abstract_inverted_index.considered, | 58 |
| abstract_inverted_index.directions. | 34 |
| abstract_inverted_index.directions: | 117 |
| abstract_inverted_index.distributed | 9, 118, 171 |
| abstract_inverted_index.fundamental | 3 |
| abstract_inverted_index.recoloring, | 39 |
| abstract_inverted_index.intermediate | 250 |
| abstract_inverted_index.intersection | 113 |
| abstract_inverted_index.most-studied | 5 |
| abstract_inverted_index.pathological | 91 |
| abstract_inverted_index.O(ω²Δ²log | 270 |
| abstract_inverted_index.assumptions), | 97 |
| abstract_inverted_index.communication | 202 |
| abstract_inverted_index.respectively, | 90 |
| abstract_inverted_index.bounded-degree | 18, 80 |
| abstract_inverted_index.communication, | 263 |
| abstract_inverted_index.synchronously. | 190 |
| abstract_inverted_index.transformation | 45 |
| abstract_inverted_index.ω+1-colorings | 286 |
| abstract_inverted_index.O(poly(Δ)log*n) | 260 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 91 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile.value | 0.45033019 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |