Geodesic
On the threshold-width of graphs
Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 2, pp. 253-268.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

For a graph class G, 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 endpoints of e are in \Ni. For the class \T\H of threshold graphs we show that \T\H-width is NP-complete and we present fixed-parameter algorithms. We also show that for each k, graphs of \T\H-width at most k are characterized by a finite collection of forbidden induced subgraphs. 
@article{JGAA_2011_15_2_a3,
     author = {Maw-Shang Chang and Ling-Ju Hung and Ton Kloks and Sheng-Lung Peng},
     title = {On the threshold-width of graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {253--268},
     publisher = {mathdoc},
     volume = {15},
     number = {2},
     year = {2011},
     doi = {10.7155/jgaa.00225},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00225/}
}
TY  - JOUR
AU  - Maw-Shang Chang
AU  - Ling-Ju Hung
AU  - Ton Kloks
AU  - Sheng-Lung Peng
TI  - On the threshold-width of graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 253
EP  - 268
VL  - 15
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00225/
DO  - 10.7155/jgaa.00225
LA  - en
ID  - JGAA_2011_15_2_a3
ER  - 
%0 Journal Article
%A Maw-Shang Chang
%A Ling-Ju Hung
%A Ton Kloks
%A Sheng-Lung Peng
%T On the threshold-width of graphs
%J Journal of Graph Algorithms and Applications
%D 2011
%P 253-268
%V 15
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00225/
%R 10.7155/jgaa.00225
%G en
%F JGAA_2011_15_2_a3
Maw-Shang Chang; Ling-Ju Hung; Ton Kloks; Sheng-Lung Peng. On the threshold-width of graphs. Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 2, pp. 253-268. doi : 10.7155/jgaa.00225. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00225/

Cité par Sources :