Metraipolis › archive › dc_22fdf4583d30

Interval graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Interval_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T14:28:32.129Z
SHA-256 of the archived text
3dcc81c3ec619615b735d5237d2f81812513adbebc91a1d74b48ea7f3945a422
Stable URL of this page
https://metraipolis.com/documento/dc_22fdf4583d30

How to cite

Interval graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Interval_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_22fdf4583d30 (Metraipolis archive dc_22fdf4583d30, sha256 3dcc81c3ec619615b735d5237d2f81812513adbebc91a1d74b48ea7f3945a422)
BibTeX
@misc{dc22fdf4583d30,
  title = {Interval graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Interval_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_22fdf4583d30; sha256 3dcc81c3ec619615b735d5237d2f81812513adbebc91a1d74b48ea7f3945a422},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Interval_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Interval graph» — https://en.wikipedia.org/wiki/Interval_graph
Wikidata Q835942 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q835942
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Interval_graph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1371127249, consultata il 2026-10-07T14:08:00.540Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fc042f54de1f973e3d88d28c7df2f6244f07db76e6eaabce0f72d97f5d337a39