A polynomial algorithm for the k-cluster problem on interval graphs

Details A polynomial algorithm for the k-cluster problem on interval graphs A polynomial algorithm for the k-cluster problem on interval graphs

2005-12-11

arxiv.org/abs/cs/0512046v3

Computer Science

Data Structures and Algorithms

12 pages, 5 figures

Scientific paper

This paper deals with the problem of finding, for a given graph and a given natural number k, a subgraph of k nodes with a maximum number of edges. This problem is known as the k-cluster problem and it is NP-hard on general graphs as well as on chordal graphs. In this paper, it is shown that the k-cluster problem is solvable in polynomial time on interval graphs. In particular, we present two polynomial time algorithms for the class of proper interval graphs and the class of general interval graphs, respectively. Both algorithms are based on a matrix representation for interval graphs. In contrast to representations used in most of the previous work, this matrix representation does not make use of the maximal cliques in the investigated graph.

Affiliated with

Also associated with

No associations

Rating

A polynomial algorithm for the k-cluster problem on interval graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A polynomial algorithm for the k-cluster problem on interval graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polynomial algorithm for the k-cluster problem on interval graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502554