The (theta, wheel)-free graphs Part IV: Induced paths and cycles
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-4280
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2020.06.002
- Title of journal
- Journal of Combinatorial Theory, Series B
- Article number
- -
- First page
- 495
- Volume
- 146
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Compliant
- Month of publication
- July
- Year of publication
- 2020
- URL
-
-
- 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)
-
A - AC (Algorithms and Complexity)
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The decomposition theorem from DOI:10.1016/j.jctb.2019.07.004 provides an excellent platform for developing new algorithmic techniques. We develop new techniques for induced cycles and paths problems. We prove a general theorem for Induced Disjoint Paths (IDP) problem for classes decomposable by clique cutsets. We also show how 2-joins interact with this problem. Finally proving that IDP (when number of paths is part of input) is polynomially-solvable for (theta, wheel)-free graphs. IDP is not known to be solvable in polytime for many classes.
Vuškovic presented this work as Invited Plenary Speaker at: Bordeaux Graph Workshop (2019), British Colloquium for Theoretical Computer Science (2020).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
