---
res:
  bibo_abstract:
  - 'In this work we introduce the graph-theoretic notion of mendability: for each
    locally checkable graph problem we can define its mending radius, which captures
    the idea of how far one needs to modify a partial solution in order to “patch
    a hole.” We explore how mendability is connected to the existence of efficient
    algorithms, especially in distributed, parallel, and fault-tolerant settings.
    It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds
    in the LOCAL model of distributed computing. One of the surprises is that in paths
    and cycles, a converse also holds in the following sense: if a problem Π can be
    solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently
    solvable but that is also O(1)-mendable. We also explore the structure of the
    landscape of mendability. For example, we show that in trees, the mending radius
    of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs
    the structure is much more diverse.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Alkida
      foaf_name: Balliu, Alkida
      foaf_surname: Balliu
  - foaf_Person:
      foaf_givenName: Juho
      foaf_name: Hirvonen, Juho
      foaf_surname: Hirvonen
  - foaf_Person:
      foaf_givenName: Darya
      foaf_name: Melnyk, Darya
      foaf_surname: Melnyk
  - foaf_Person:
      foaf_givenName: Dennis
      foaf_name: Olivetti, Dennis
      foaf_surname: Olivetti
  - foaf_Person:
      foaf_givenName: Joel
      foaf_name: Rybicki, Joel
      foaf_surname: Rybicki
      foaf_workInfoHomepage: http://www.librecat.org/personId=334EFD2E-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-6432-6646
  - foaf_Person:
      foaf_givenName: Jukka
      foaf_name: Suomela, Jukka
      foaf_surname: Suomela
  bibo_doi: 10.1007/978-3-031-09993-9_1
  bibo_volume: 13298
  dct_date: 2022^xs_gYear
  dct_identifier:
  - UT:000876977400001
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9783031099922
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: Local mending@
...