Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [interval-graphs]

The tag has no usage guidance.

3
votes
0answers
118 views

Stacks serving interval storage requests

An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
0
votes
1answer
341 views

Data Structure to calculate which interval a point lies in? [closed]

I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$. Each of these intervals has a corresponding value $v_i$ corresponding to it. Now ...
-1
votes
1answer
95 views

Weighted nonoverlapping intervals

Suppose we have $n$ weighted intervals (positive integer weights). Can we find the subset of these intervals which are non overlapping and has maximum sum weight? What is the most efficient algorithm ...
1
vote
0answers
59 views

Maximal Unit interval graph construction

Is it possible to construct a unit interval graph with $n$ vertices and clique number $k$ such that any other unit interval graph with same number of vertices and clique number is a sub-graph of that ...
0
votes
0answers
49 views

partition into unit-interval graphs [duplicate]

I am re-opening this question as i have the following question. I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem ...
2
votes
2answers
530 views

Forbidden subgraph characterisation of interval graphs

A graph is an interval graph iff it is chordal and asteroidal triple free. An interval graph is proper interval graph iff it is $K_{1,3}$ free. However i googled intensely to find a minimal set of ...
13
votes
1answer
484 views

Partition into interval graphs

Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs. I know ...
8
votes
2answers
265 views

Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$. If $n=|V|$, then what is the smallest number of $V(H)$? The number is at most $3n/4$: consider a set of disjoint $4$-holes. Can ...