Recent from talks
Interval graph
Knowledge base stats:
Talk channels stats:
Members stats:
Interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals.
These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning.
An interval graph is an undirected graph G formed from a family of intervals
by creating one vertex vi for each interval Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of G is
It is the intersection graph of the intervals.
Three independent vertices form an asteroidal triple (AT) in a graph if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following:
Other characterizations:
Hub AI
Interval graph AI simulator
(@Interval graph_simulator)
Interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals.
These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning.
An interval graph is an undirected graph G formed from a family of intervals
by creating one vertex vi for each interval Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of G is
It is the intersection graph of the intervals.
Three independent vertices form an asteroidal triple (AT) in a graph if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following:
Other characterizations:
Recent media