| 日時 | 3月 19日 (土) 午前１０時から午後５時半頃まで |
| 会場 | 日本大学 文理学部 ８号館１階 レクチャーホール |
| 〒156-0045 東京都世田谷区桜上水3-25-40 | |
| 世話役 | 戸田誠之助 (田中圭介グループ) |
| 内容 | chordal graphに関連した計算問題やアルゴリズムを中心に、 以下の講演と新たな課題探求に向けたディスカッションを行う予定です。 |
| 交通 | 京王線・下高井戸駅（または桜上水駅）下車；新宿から１５分程度 http://www.chs.nihon-u.ac.jp/index-con/access_f.html http://www.chs.nihon-u.ac.jp/bunri-info/campasmap.html |
| 下高井戸から来た場合、正門の前を通り過ぎて（キャンパスに 入らず）、さらに通用門の真横の道を（キャンパスに入らずに） しばらく行くと８号館の玄関に到達します。玄関から入ってすぐ 右手にある部屋です。 |
| 10:00 -- 11:20 | Computing automorphism groups of chordal graphs whose simplicial components are of small size |
| 発表： 戸田誠之助 (日大文理) 概要： 小さなサイズの単体成分へと分解可能な任意のchordal graphに対して、 その自己同型群が多項式時間計算可能であることをお話致します。 | |
| 11:30 -- 12:30 | 2-リンクパズルの多項式時間解法 |
| 発表： 牧野格三 (東工大) 概要： 本研究ではパズルの一種「ナンバーリンク」について、それに対応する グラフ理論的な問題「k-リンクパズル」を定義した。さらに、1-リンク パズルが多項式時間で解けることを利用し、2-リンクパズルのサイズを 3×(偶数)や4×(偶数)に限定した問題に対する多項式時間解法を与えた。 | |
| 12:30 -- 13:30 | 昼休み |
| 13:30 -- 15:00 | On the Laminar Structure of Ptolemaic and Distance Hereditary Graphs |
| 発表： ○上原隆平 (JAIST), 宇野裕之 (大阪府立大学) 概要： Ptolemaic graphs are graphs that satisfy ptolemaic inequality for any four vertices. The graph class is coincident with the intersection of chordal graphs and distance hereditary graphs. The graph class can be seen as a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a canonical tree representation based on a laminar structure of cliques. Hence simple linear algorithms for recognition and for the graph isomorphism problem are obtained. The tree representation is constructed in linear time from the perfect elimination ordering obtained by the lexicographic breadth search. The tree representation gives a simple intersection model for ptolemaic graphs. The results are also extended to distance hereditary graphs. | |
| 15:15 -- 16:45 | On precoloring extension problem |
| 発表： 名古屋孝幸 (東京電機大学) 概要： In the precoloring extension problem (PREXT) a graph is given with some of the vertices having a preassigned color and it has to be decided whether this coloring can be extended to a proper coloring of the graph with a given number of colors. PREXT is NP-complete for unit interval (and thus for chordal) graphs. On the other hand, the problem can be solved in polynomial time for chordal graphs with bounded clique number. In this talk, I will survey some known results on PREXT, and state some open questions. | |
| 15:15 -- 16:45 | ディスカッション |