Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431261 | Journal of Discrete Algorithms | 2015 | 8 Pages |
Abstract
We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ton Kloks, Sheung-Hung Poon, Chin-Ting Ung, Yue-Li Wang,