CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Editing the simplest graphs

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Olof Mogren (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Lecture Notes in Computer Science: 8th International Workshop on Algorithms and Computation WALCOM 2014, Lecture Notes in Computer Science (0302-9743). Vol. 8344 (2014), p. 249-260.
[Konferensbidrag, refereegranskat]

We study the complexity of editing a graph into a target graph with any fixed critical-clique graph. The problem came up in practice, in mining a huge word similarity graph 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.

Nyckelord: cluster editing, word cluster, fixed-parameter tractability, NP-completeness



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2014-03-07. Senast ändrad 2015-07-06.
CPL Pubid: 194624

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)