New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs.
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 103331
- Type
- D - Journal article
- DOI
-
10.1137/15M1039468
- Title of journal
- SIAM Journal on Discrete Mathematics
- Article number
- -
- First page
- 1685
- Volume
- 30
- Issue
- 3
- ISSN
- 08954801
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2016
- URL
-
https://doi.org/10.1137/15M1039468
- 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
-
1
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper introduced a novel and powerful geometric representation for the well-studied class of tolerance graphs, which changed the way we interpret these graphs and enabled the design of the first polynomial-time algorithm for the dominating set problem. This resolved one of the two most famous problems on tolerance graphs which remained open since 1982 (the second one is Hamiltonian Cycle), thus achieving a significant impact to the state of the art in the area of algorithmic graph theory.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -