Signed and minus clique-transversal functions on graphs |
| |
| Authors: | Chuan-Min Lee Maw-Shang Chang |
| |
| Affiliation: | a Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Rd., Guishan District, Taoyuan County 333, Taiwan, ROC
b Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Hsiung, Chiayi 621, Taiwan, ROC |
| |
| Abstract: | A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function  (respectively, {−1,1}) such that ∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs. |
| |
| Keywords: | Graph algorithms Minus clique-transversal functions Strongly chordal graphs Planar graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
