Output details
11 - Computer Science and Informatics
University of Leeds
Output title
Colouring AT-Free Graphs
Type
E - Conference contribution
Name of conference/published proceedings
Lecture Notes in Computer Science: 20th Annual European Symposium on Algorithms (ESA 2012)
Volume number
7501
Issue number
-
First page of article
707
ISSN of proceedings
0302-9743
Year of publication
2012
URL
-
Number of additional authors
1
Additional information
<13>Graph colouring is a benchmark problem in algorithmics, practically important for frequency assignment. We invented the asteroidal decomposition of graphs, which enabled us to decide in polynomial time whether AT-free graphs can be k-coloured, settling a 15-year problem. Consequently, we are working to (i) prove the power of asteroidal width, which we believe surpasses treewidth, suggesting paradigm shifting significance; (ii) exploit this decompositions to solve a variety of problems, including graph homomorphism. Since our method is so general it extends to practically important graphs classes. ESA is among the top five algorithms conferences worldwide.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
1
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
