The Maximum Clique Problem in Multiple Interval Graphs

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

22 pages

Scientific paper

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $t\geq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $t\geq 4$ and polynomial-time solvable when $t\leq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The Maximum Clique Problem in Multiple 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 The Maximum Clique Problem in Multiple Interval Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Maximum Clique Problem in Multiple Interval Graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-334644

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.