区間グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 区間グラフの意味・解説 

区間グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/03/06 10:20 UTC 版)

区間グラフとは、グラフ理論のグラフの一種であり、区間集合の区間の重複を表す交差グラフである。 それぞれの区間が頂点に対応し、辺は区間同士の重複(交差)関係を表す。


  1. ^ a b Lekkerkerker & Boland (1962)
  2. ^ a b c (Fishburn 1985)
  3. ^ Fulkerson & Gross (1965)
  4. ^ a b Gilmore & Hoffman (1964)
  5. ^ McKee & McMorris (1999)
  6. ^ Brandstädt, Le & Spinrad (1999)
  7. ^ Golumbic (1980).
  8. ^ Eckhoff (1993)
  9. ^ Roberts (1969); Gardi (2007)
  10. ^ Faudree, Flandrin & Ryjáček (1997), p. 89.
  11. ^ Proskurowski, Andrzej; Telle, Jan Arne (1999). “Classes of graphs with restricted interval models”. Discrete Mathematics & Theoretical Computer Science. 3 (4): 167–176. 
  12. ^ Beyerl, Jeffrey; Jamison, Robert (2008). “Interval graphs with containment restrictions”. Congressus Numerantium 191 (2008): 117–128. arXiv:1109.6675. Bibcode 2011arXiv1109.6675B. 
  13. ^ 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]. 
  14. ^ Cohen (1978, pp. ix-10)
  15. ^ Cohen (1978, pp. 12–33)
  16. ^ Bar-Noy et al. (2001).
  17. ^ 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 
  18. ^ Zhang et al. (1994).
  19. ^ Golumbic & Shamir (1993).
  20. ^ Villanger et al. (2009).
  21. ^ Bliznets et al. (2014).
  22. ^ Bodlaender (1998).


「区間グラフ」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「区間グラフ」の関連用語

区間グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



区間グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの区間グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS