Block-graph width |
| |
Authors: | Maw-Shang Chang |
| |
Affiliation: | a Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 62107, Taiwanb Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien 97401, Taiwan |
| |
Abstract: | Let G be a class of graphs. A graph G has G-width k if there are k independent sets N1,…,Nk in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in Ni. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained. |
| |
Keywords: | Probe graphs Parameterized algorithms Block graphs |
本文献已被 ScienceDirect 等数据库收录! |
|