Characterising bounded expansion by neighbourhood complexity
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 193
- Type
- D - Journal article
- DOI
-
10.1016/j.ejc.2018.08.001
- Title of journal
- European Journal of Combinatorics
- Article number
- -
- First page
- 152-168
- Volume
- 75
- Issue
- -
- ISSN
- 0195-6698
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2018
- URL
-
http://eprints.bbk.ac.uk/id/eprint/24753/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
1 - Algorithms, Verification and Software
- Citation count
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- We proved a novel characterisation of bounded expansion classes. The preprint of this paper directly led to a linear kernel for DISTANCE-r DOMINATING SET in these graph classes (Drange et. al, STACS'16), generalising a number of important results on planar, bounded-degree and excluded-minor classes. This work has subsequently been generalised by others in several interesting ways (Eickmeyer et al., ICALP '17 and Pilipczuk et al., LICS'18). Our proof techniques further inspired results on the dimension of posets (Joret et al., Combinatorica. 2018 Oct 1;38(5):1129-48).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -