区間グラフ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/03/06 10:20 UTC 版)
区間グラフとは、グラフ理論のグラフの一種であり、区間集合の区間の重複を表す交差グラフである。 それぞれの区間が頂点に対応し、辺は区間同士の重複(交差)関係を表す。
- ^ a b Lekkerkerker & Boland (1962)
- ^ a b c (Fishburn 1985)
- ^ Fulkerson & Gross (1965)
- ^ a b Gilmore & Hoffman (1964)
- ^ McKee & McMorris (1999)
- ^ Brandstädt, Le & Spinrad (1999)
- ^ Golumbic (1980).
- ^ Eckhoff (1993)
- ^ Roberts (1969); Gardi (2007)
- ^ Faudree, Flandrin & Ryjáček (1997), p. 89.
- ^ Proskurowski, Andrzej; Telle, Jan Arne (1999). “Classes of graphs with restricted interval models”. Discrete Mathematics & Theoretical Computer Science. 3 (4): 167–176.
- ^ Beyerl, Jeffrey; Jamison, Robert (2008). “Interval graphs with containment restrictions”. Congressus Numerantium 191 (2008): 117–128. arXiv:1109.6675. Bibcode 2011arXiv1109.6675B.
- ^ Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (2015年10月14日). “On the Classes of Interval Graphs of Limited Nesting and Count of Lengths”. arXiv:1510.03998 [cs.DM].
- ^ Cohen (1978, pp. ix-10)
- ^ Cohen (1978, pp. 12–33)
- ^ Bar-Noy et al. (2001).
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7
- ^ Zhang et al. (1994).
- ^ Golumbic & Shamir (1993).
- ^ Villanger et al. (2009).
- ^ Bliznets et al. (2014).
- ^ Bodlaender (1998).
[続きの解説]
「区間グラフ」の続きの解説一覧
- 1 区間グラフとは
- 2 区間グラフの概要
- 3 応用
- 4 参考文献
- 5 外部リンク
- 区間グラフのページへのリンク