弦グラフ

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)

弦化(Chordal completion)と木幅

任意のグラフGの弦化とは、Gを部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる^[12]^[13]。 Gの木幅はクリークのサイズが最小となるような弦化が施されたGの最大クリークの頂点数-1である。 k-木は木幅をkより大きくしなければ辺を追加できないグラフである。したがって、k-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる^[14]。

参考文献

Agnarsson, Geir (2003), “On chordal graphs and their chromatic polynomials”, Mathematica Scandinavica 93 (2): 240–246, MR2009583 .
Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), “Almost all chordal graphs split”, J. Austral. Math. Soc., A 38 (2): 214–221, doi:10.1017/S1446788700023077, MR0770128 .
Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), “Recognizing chordal probe graphs and cycle-bicolorable graphs”, SIAM Journal on Discrete Mathematics 21 (3): 573–591, doi:10.1137/050637091 .
Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), “Two strikes against perfect phylogeny”, Proc. of 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Computer Science, 623, pp. 273–283, doi:10.1007/3-540-55719-9_80 .
Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), “Enumerating and characterizing the perfect elimination orderings of a chordal graph”, Theoretical Computer Science 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4 .
Dirac, G. A. (1961), “On rigid circuit graphs”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25: 71–76, doi:10.1007/BF02992776, MR0130190 .
Fomin, Fedor V.; Villanger, Yngve (2013), “Subexponential Parameterized Algorithm for Minimum Fill-In”, SIAM J. Comput. 6: 2197–2216, arXiv:1104.2230, doi:10.1137/11085390X .
Fulkerson, D. R.; Gross, O. A. (1965), “Incidence matrices and interval graphs”, Pacific J. Math. 15: 835–855, doi:10.2140/pjm.1965.15.835 .
Gavril, Fănică (1974), “The intersection graphs of subtrees in trees are exactly the chordal graphs”, Journal of Combinatorial Theory, Series B 16: 47–56, doi:10.1016/0095-8956(74)90094-X .
Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press .
Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), “Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing”, Theoretical Computer Science 234: 59–84, doi:10.1016/S0304-3975(97)00241-7 .
Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), “Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs”, SIAM J. Comput. 5: 1906–1922, doi:10.1137/S0097539796303044 .
Maffray, Frédéric (2003), “On the coloration of perfect graphs”, in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1 .
Parra, Andreas; Scheffler, Petra (1997), “Characterizations and algorithmic applications of chordal graph embeddings”, Discrete Applied Mathematics 79 (1-3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR1478250 .
Patil, H. P. (1986), “On the structure of k-trees”, Journal of Combinatorics, Information and System Sciences 11 (2–4): 57–64, MR966069 .
Rose, D.; Lueker, George; Tarjan, Robert E. (1976), “Algorithmic aspects of vertex elimination on graphs”, SIAM Journal on Computing 5 (2): 266–283, doi:10.1137/0205021 .
Seymour, P. D.; Weaver, R. W. (1984), “A generalization of chordal graphs”, Journal of Graph Theory 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR742878 .
Szwarcfiter, J.L.; Bornstein, C.F. (1994), “Clique graphs of chordal and path graphs”, SIAM Journal on Discrete Mathematics 7: 331–336, doi:10.1137/s0895480191223191 .