Geodesic
Editing Simple Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014 , Tome 18 (2014) no. 4, pp. 557-576.

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

We study the complexity of turning a given graph, by edge editing, into a target graph whose critical-clique graph is any fixed graph. The problem came up in practice, in an effort of mining huge word similarity graphs for well structured word clusters. It also adds to the rich field of graph modification problems. We show in a generic way that several variants of this problem are in SUBEPT. As a special case, we give a tight time bound for edge deletion to obtain a single clique and isolated vertices, and we round up this study with NP-completeness results for a number of target graphs.
DOI : 10.7155/jgaa.00337
Keywords: graph editing, critical-clique graph, word cluster, subexponential parameterized algorithm, NP-completeness 
@article{JGAA_2014_18_4_a4,
     author = {Peter Damaschke and Olof Mogren},
     title = {Editing {Simple} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {557--576},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2014},
     doi = {10.7155/jgaa.00337},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00337/}
}
TY  - JOUR
AU  - Peter Damaschke
AU  - Olof Mogren
TI  - Editing Simple Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 557
EP  - 576
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00337/
DO  - 10.7155/jgaa.00337
LA  - en
ID  - JGAA_2014_18_4_a4
ER  - 
%0 Journal Article
%A Peter Damaschke
%A Olof Mogren
%T Editing Simple Graphs
%J Journal of Graph Algorithms and Applications
%D 2014
%P 557-576
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00337/
%R 10.7155/jgaa.00337
%G en
%F JGAA_2014_18_4_a4
Peter Damaschke; Olof Mogren. Editing Simple Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
					, Tome 18 (2014) no. 4, pp. 557-576. doi : 10.7155/jgaa.00337. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00337/

Cité par Sources :