Some characterizations of doubly chordal graphs |
| |
| Authors: | Mahnhoon Lee Changhwa Kim |
| |
| Institution: | 1. Computer Science Department, Kangnung National University, Kangnung, 210-702, Kangwon, Korea
|
| |
| Abstract: | Many optimization problems like domination and Steiner tree are NP-complete onchordal graphs but can be solved in polynomial time ondoubly chordal graphs. Investigating properties of doubly chordal graphs probably help to design efficient algorithms for the graphs. We present some characterizations of doubly chordal graphs, which are based on clique matrices and neighborhood matrices. It is also mentioned how adoubly perfect elimination ordering of a doubly chordal graph can be computed from the results. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
