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.
Original language | English |
---|---|
Pages (from-to) | 21-28 |
Number of pages | 8 |
Journal | Journal of Discrete Algorithms |
Volume | 30 |
DOIs | |
Publication status | Published - 1 Jan 2015 |
Externally published | Yes |
Keywords
- Chordal bipartite graph
- Induced matching
- Permutation graph
- Strong chromatic index
- Tree-cograph
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics