この記事は文字列アドベントカレンダー5日目の記事です． qiita.com はじめに 文字列Advent Calendarと言いつつ，木について書いていこうかなと思います． まあ，文字列ガチ勢から見れば，根付き木は実質文字列なので，このCalendarで書いてもみんな喜んでく…

今回はグラフの性質のお話ではなくPEOを求めるためのアルゴリズムのお話をします． MCSとLex BFSというアルゴリズムのお話をします． chordal graphの性質についてはこの2つのアルゴリズムを説明した後にもまだまだ書きます． 今回は長くなるので，2回に分け…

3回目のChordal Graph回です． 知識的にストックがあるのと，始めたばかりでやる気があるので，更新ペースがめちゃくちゃ早いです． 今回はPerfect elimination orderingについて説明します． Perfect elimination ordering (PEO) もchordal graphの重要で面…

なんか意外に反響があった（アクセスログを見ていたらみんなが見ていてくれた）のでやる気を出したのと，少し今回の内容が簡単だったのもあって が〜っと書いてしまいました．2回目のChordal Graph回です． 今回は次回にやる予定のPerfect elimination order…

chocobaby-aporo.hatenablog.com Chordal Graph回の第一回目です．今回はMinimal vertex separatorsを紹介します． Minimal vertex separators まず，$G = (V, E)$中の頂点集合$S \subseteq V$が，vertex separator (separator)とは 次のような2頂点$u, v$が…

最近Chordal Graphがマイブームです． このシリーズの記事でわからないところやこれ間違っているぞっというのがあったら Twitterで教えてくれると僕が喜びます． Twitter ID: kazu0x17 Chordal Graphとは Chordal Graphとは任意の長さ4以上のサイクルに対し…