2
$\begingroup$

A graph is called a circular-arc graph if each of its vertices can be assigned to a circular arc such that two vertices are adjacent iff their respective arcs have a non-empty intersection. Analogously, a graph is an interval graph if we can assign each of its vertices to intervals on a line in the above fashion. Note that interval graphs are a subclass of circular-arc graphs.

Wikipedia states that interval/circular-arc graphs are important in the modeling of (periodic) resource allocations problems in operations research. Can you provide a concrete example of such a problem and how it is modeled to CA/interval graphs? The problem should conceivably occur in practice.

$\endgroup$
2
  • 1
    $\begingroup$ If you think about the intervals as times when certain jobs need to be done, then the graph with an edge between two jobs that have overlap in their active times are interval graphs or circular arc graphs. $\endgroup$ – Louis May 11 '14 at 19:06
  • $\begingroup$ I don't have a concrete application, or I'd make an answer, but I assume that this is the idea. $\endgroup$ – Louis May 11 '14 at 19:31
2
$\begingroup$

Making Louis' comment into an answer:

Given a set of intervals (interval system) $\mathcal{I} = \{ [x_1, x_2] ,\dots, [x_{2n-1}, x_{2n}] \}$. Each of the $n$ intervals corresponds to the time period a certain job is being worked on. Now, we want to find all time periods in which the number of concurrently active jobs is maximal. These time periods happen to correspond to the maxcliques of maximal size of the intersection graph $G(\mathcal{I}) = (\mathcal{I} , E)$ with $E$ being defined as $$ ([a,b] , [c,d]) \in E \iff [a,b] \cap [c,d] \neq \emptyset $$ The closed neighborhood of a vertice $v$ in a graph $G$ is defined as $$ N[v] := \{ u \in V(G) : \{v,u\} \in E \} \cup \{v\}$$ It is known that for any interval graph every maxclique can be characterized as the intersection of two neighborhoods, i.e. for each maxclique $C$ of $G$ there exist some $u,v \in V(G)$ s.t. $C = N[u] \cap N[v]$.

With this we can easily devise an efficient algorithm to find the wanted time periods.

If you have any other answers along these lines I'd be happy to hear them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.