Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

The Complexity of Clustering in Planar Graphs

J. Mark Keil1, Timothy B. Brecht1
1Department of Computational Science University of Saskatchewan Saskatoon, Canada S7N OWO
  • Published: 30/04/1991

Abstract

An \(h\)-cluster in a graph is a set of \(h\) vertices which maximizes the number of edges in the graph induced by these vertices. We show that the connected \(h\)-cluster problem is NP-complete on planar graphs.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
J. Mark Keil, Timothy B. Brecht. The Complexity of Clustering in Planar Graphs[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 009. 155-159. DOI: .