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

Editing simple graphs

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Olof Mogren (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Journal of Graph Algorithms and Applications (1526-1719). Vol. 18 (2014), 4, p. 557-576.
[Artikel, refereegranskad vetenskaplig]

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.



Denna post skapades 2015-01-08. Senast ändrad 2015-02-11.
CPL Pubid: 210182

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)

Ämnesområden

Diskret matematik

Chalmers infrastruktur