Graph could be:

------

------ ------ ------ ------

---------------------------------------------------------------------------

these are nodes/vertices/intervals on the infinite line.

where 1st and 2nd vertices are overlapping (adjacent) --> clique of 2 (although they would be better spread out but incapable of doing this here)

1 (10 pts] The vertices of a linear unit disk graph G are unit length intervals (i.e., of length 1) placed in arbitrary positions on an infinite line. Two nodes (i.e., intervals) are adjacent iff they overlap. The clique number of G, denoted by w(G), is the size of the largest number of paitwise overlapping intervals. 1. [2 pts) Apply the greedy sequential coloring algorithm discussed in class to such an interval unit disk graph. In the pseudo-code place the vertices in order of their left endpoint, . 1 2. [4 pts] Give an algorithm to compute the clique number wG). 3. [4 pts] Now assume w(G) is known. Consider the following sequential algorithm. When a new interval I is presented whose left endpoint a, it uses a color in {1,...,W(G)} if the floor lan] of a; is even, and uses a color in {2w(G)+1,..., 2w(G)} if the floor [91] of a; is odd. Prove that the algorithm colors the graph correctly. What is the competitive ratio of the algorithm? (By competitive ratio we mean the ratio achieved by our algorithm divided by the optimal one.) 1 (10 pts] The vertices of a linear unit disk graph G are unit length intervals (i.e., of length 1) placed in arbitrary positions on an infinite line. Two nodes (i.e., intervals) are adjacent iff they overlap. The clique number of G, denoted by w(G), is the size of the largest number of paitwise overlapping intervals. 1. [2 pts) Apply the greedy sequential coloring algorithm discussed in class to such an interval unit disk graph. In the pseudo-code place the vertices in order of their left endpoint, . 1 2. [4 pts] Give an algorithm to compute the clique number wG). 3. [4 pts] Now assume w(G) is known. Consider the following sequential algorithm. When a new interval I is presented whose left endpoint a, it uses a color in {1,...,W(G)} if the floor lan] of a; is even, and uses a color in {2w(G)+1,..., 2w(G)} if the floor [91] of a; is odd. Prove that the algorithm colors the graph correctly. What is the competitive ratio of the algorithm? (By competitive ratio we mean the ratio achieved by our algorithm divided by the optimal one.)