On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

被引：1
作者：
Kloks, Ton [1 ]
Poon, Sheung-Hung [2 ]
Ung, Chin-Ting [1 ]
Wang, Yue-Li [3 ]
机构：
[1] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu, Taiwan
[2] Inst Teknol Brunei, Sch Comp & Informat, Darussalam, Brunei
[3] Natl Taiwan Univ Sci & Technol, Dept Informat Management, 43,Sec 4,Keelung Rd, Taipei 106, Taiwan
来源：
JOURNAL OF DISCRETE ALGORITHMS | 2015年 / 30卷
关键词：
Strong chromatic index; Induced matching; Tree-cograph; Permutation graph; Chordal bipartite graph;
D O I：
10.1016/j.jda.2014.11.004
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码：21 / 28
页数：8
相关论文
共 39 条
1234