Geodesic
Parameterized Algorithms for (r,l)-Partization
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012 , Tome 17 (2013) no. 2, pp. 129-146.

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

We consider the (r,l)-Partization problem of finding a set of at most k vertices whose deletion results in a graph that can be partitioned into r independent sets and l cliques. Restricted to perfect graphs and split graphs, we describe sequacious fixed-parameter tractability results for (r,0)-Partization, parameterized by k and r. For (r,l)-Partization where r+l=2, we describe an O*(2k) algorithm for perfect graphs. We then study the parameterized complexity hardness of a generalization of the Above Guarantee Vertex Cover by a reduction from (r,l)-Partization.
DOI : 10.7155/jgaa.00288
Keywords: Parameterized complexity, Odd cycle transversal, r-Partization, Bicochromatization, Perfect graphs, Split graphs, Generalized above guarantee vertex cover 
@article{JGAA_2013_17_2_a4,
     author = {R. Krithika and N. Narayanaswamy},
     title = {Parameterized {Algorithms} for {(r,l)-Partization}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {129--146},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2013},
     doi = {10.7155/jgaa.00288},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00288/}
}
TY  - JOUR
AU  - R. Krithika
AU  - N. Narayanaswamy
TI  - Parameterized Algorithms for (r,l)-Partization
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 129
EP  - 146
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00288/
DO  - 10.7155/jgaa.00288
LA  - en
ID  - JGAA_2013_17_2_a4
ER  - 
%0 Journal Article
%A R. Krithika
%A N. Narayanaswamy
%T Parameterized Algorithms for (r,l)-Partization
%J Journal of Graph Algorithms and Applications
%D 2013
%P 129-146
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00288/
%R 10.7155/jgaa.00288
%G en
%F JGAA_2013_17_2_a4
R. Krithika; N. Narayanaswamy. Parameterized Algorithms for (r,l)-Partization. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
					, Tome 17 (2013) no. 2, pp. 129-146. doi : 10.7155/jgaa.00288. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00288/

Cité par Sources :