Intervallgraph

Die Intervallgraphen bilden in der Graphentheorie eine spezielle Klasse von Graphen.

Die erste Erwähnung findet man bei György Hajós 1957. Einen wesentlichen Schub bekam das Interesse an Intervallgraphen durch einen Vorstoß von Seymour Benzer 1959, der eine These zur Struktur von Genen überprüfen wollte. Zu den zeitgenössischen Anwendungen gehören unter anderem Probleme des Scheduling, archäologische Seriation, Verhaltenspsychologie, Temporallogik, Schaltungsdesign und das Human Genome Project.

1. ↑ G. Hajös: Über eine Art von Graphen. In: Intern. Math. Nachr. 11. Jahrgang, Nr. 65, 1957. 
2. ↑ Seymour Benzer: On the topology of the genetic fine structure. In: Proceedings of the National Academy of Sciences. 45. Jahrgang, Nr. 11, 1959, S. 1607, PMC 222769 (freier Volltext) – (englisch). 
3. ↑ David Kendall: Incidence matrices, interval graphs and seriation in archeology. In: Pacific Journal of mathematics. 28. Jahrgang, Nr. 3, 1969, S. 565–570 (englisch, msp.org). 
4. ↑ Clyde H. Coombs, J. E. Smith: On the detection of structure in attitudes and developmental processes. In: Psychological Review. 80. Jahrgang, Nr. 5, 1973, S. 337 (englisch, apa.org). 
5. ↑ Jürgen Dorn: Temporal reasoning in sequence graphs. 10th National Conference on Artificial Intelligence (AAAI 92). In: AAAI-92 : proceedings / tenth National Conference on Artificial Intelligence, July 12-16, 1992. American Association for Artificial Intelligence, Menlo Park, CA 1992, S. 735–740 (englisch, aaai.org [PDF]). 
6. ↑ Martin Charles Golumbic, Ron Shamir: Complexity and algorithms for reasoning about time: A graph-theoretic approach. In: Journal of the ACM (JACM). 40. Jahrgang, Nr. 5, 1993, S. 1108–1133 (englisch, acm.org). 
7. ↑ Richard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology. twenty-fifth annual ACM symposium on Theory of computing. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993, S. 278–285 (englisch, acm.org).