Counting Perfect Matchings and the Switch Chain
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-4489
- Type
- D - Journal article
- DOI
-
10.1137/18M1172910
- Title of journal
- SIAM Journal on Discrete Mathematics
- Article number
- -
- First page
- 1146
- Volume
- 33
- Issue
- 3
- ISSN
- 0895-4801
- Open access status
- Compliant
- Month of publication
- July
- Year of publication
- 2019
- 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
-
1
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- We consider the switch chain for perfect matchings on classes containing non-bipartite graphs. This led to new graph classes, among them odd-chordal graphs (a natural generalization of chordal bipartite graphs and strongly chordal graphs), quasi-monotone and quasi-chain graphs. The new quasi-operator on graph classes, resembled only by the probe-operator, has initialised further research into quasi-classes, similar to the many publications on probe graphs. The article tightens the gap between classes for which the switch chain mixes rapidly and graphs on which it is torpid. The paper has triggered new work on reconfiguration problems, such as arXiv:1904.06184.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
