構造的グラフに対するアルゴリズムの工学的研究
著者
西関 隆夫
:.ヽ･J I
･-工霊鳥i･鯖轄i:]';
I , - 1 ･ ､･-′ / ､･-′､･-′-
_.-_-/-ノ′ r / / Ir ′/ ′二･一 --:㍉了,-I/i:.･
ヽ,.I 1. L LJ rLI. -′' :∼ fi /?1 1年軒平成1強度承学研究費鰯右壷議果報告軒
Ar. --_ /基盤研究(C)(2)課題番浄;1368q336
Y∼･し -ゝJLt Lヽ 才 一",. ノ. ･ '工,,言, ;＼し､構造的グラフ樗対する
アルゴリズムの工学的研究
LJllttJ ILLJ.,JJ IJHJILJllLJJILJJJ tJJJ IJffⅢ
00021006741
附属図書館
ー:5.5 ノ; ･{Y:･ 二∴∴
:'･'醜1頭朝
ゝ ′ 一一一㌧-ヽ ′▲ ･叫工/llti..一･ 一t I ･･ 一､_､ゝ ,JrJ. I. 一一一ヽ■ ＼ ●!一､ . 1代表研究者 西関 隆夫
海北棉幣院情報
等 宗一き′. {苦言 ､,. ㌔ I.ヽ▲ I l･･1-i:I-. ∫ r-･i･ i科学研究科･教授)
･掟:.声長二 . ;ノ∴二㌢∴ r k ･ ･ . -∼ ㌦ 労 B J 一 . -一 ㍉ _ i . ∼ ㍉ ′ ･ ノ ㍉ r . ∵ . . j f平
･ ■ ･ . ナ . A r t -ノ ､ ′ ′ ノ I . r J , / A . ∼ . , ･ q I ㌔ ′ 7 -ダ ー ー ] ′ ･ ･ l 鼻 L f 1 -･ ' ･ - ● 一平成11年度∼平成12年度科学研究費補助金成果報告書
基盤研究(C)(2)課題番号: 11680336
構造的グラフに対する
アルゴリズムの工学的研究
平成13年3月
代表研究者 西関 隆夫
(東北大学 大学院情報科学研究科･教授)
はしがき
本研究成果報告書は,平成11年度と, 12年度に文部省より交付された科学研究費補助
金･基盤研究(C) (2) ｢構造的グラフに対するアルゴリズムの工学的研究｣の研究成果を,
国内外において発表してきた研究論文に基づき取りまとめたものである0
本研究では,木,直並列グラフ,部分k一木等の構造的グラフに対し,彩色問題,素な通
関選,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計す
るばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を
行った｡まず,部分k-*に対しては,辺色彩問題を一般化したlg,f]辺彩色問題を解く多項式時
間アルゴリズム,全彩色間選を解く線形時間アルゴリズム,辺素な道問題をある特定の条
件下で多項式時間で解くアルゴリズム,点ランク付け問題を多項式時間で解く逐次アルゴ
リズム, 0(logn)時間で解く並列アルゴリズムの開発に成功したoまた,直並列グラフの
辺素な道問題を見つけそのNP一完全性の証明にも成功した｡
木に対しては,一般化ランク付け問題を0(n210g△)時間で解くアルゴリズムを与え,
また平面グラフ上で一`非交差"なスタイナ林を求める問題を,すべてのスタイナ木の端子
が2つの面にしかないとき, 0(nlogn)時間で解くアルゴリズムも与えた｡直並列グラフに対しては,辺彩色問題を線形時間で解く逐次アルゴリズムを与えるとと
もに, 0(△n/logn)台のプロセッサーを用いて0(logn)時間で解く並列アルゴリズムを与えた｡どちらのアルゴリズムも計算時間は比例定数の範囲内で最適である｡
また,グラフ描画アルゴリズムでは,平面グラフの3種類の描画を求める線形アルゴリ
ズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も
与えた｡本研究は,構造的グラフに対する効率的アルゴリズムの統一的設計法の開発を目指し研
究を行ってきたが,これまでさまざまな問題に対するより高速なアルゴリズムの開発に成
功しており,一般の辺素部分グラフ分解問題に対する効率のよいアルゴリズムの統一的理
論構築のために基盤作りに十分な成果をあげることができた｡この研究報告書が,これら
の関連分野の研究者に少しでもお役に立てれば幸いである｡
平成13年3月
研究課選名
構造的グラフに対するアルゴリズムの工学的研究
研究軌織
研究代表者
西関 隆夫(東北大学大学院･情報科学研究科･教授)
研究分担者
周 暁 (東北大学大学院･情報科学研究科･助教授)
研究経費
平成11年度 2,500千円
平成12年度1,100千円
計 3,600千円研究発表リスト
学術論文等
1. Y. Kusakari, H･ SUB;uki, T･ Nishizeki HA shortest pair of paths on the plane with
obstaclesand crosslngareaS,n Computation Geometry & Applications, Vol･9, No･2,
pp.15ト170, 1999･
2. X. Zhou and T. Nishizeki, "Edge-coloring and I-coloring for various cla58eS Ofgraphs,"
Journal of Graph Algorithms and Applications) Ⅵ)1･3, No･lI pp･1-18I 1999･
3. S. Isobe, X･ Zhou and T･ Nishizeki, ㍑A polynomial-timealgorithm for丘nding to-talcolorings of partialk-trees,n InternationalJournalof Foundations of Computer Science, Vbl.10, No.2, pp･17ト194, 1999･
4. Md. S. Rahman, S. Nakano and T. Nishizeki, "A linearalgorithm for bend-Optimal
orthogonal drawings of triconnected cubic plane graphs,刀 J･ of Graph Algorithms
and Applications,Vbl.3, No･3, pp･31-62, 1999･
5. K. Millra, D. Takahashi, S･ Nakanoand T･ Nishizeki, HA linear-timealgorithm to find four independent spanning trees in four connected planar graphs," International Journalof Foundations of Computer Science, Vol･10, No･2, pp･1951210, 1999･ 6. X. Zhou, S. Tamuraand T. Nishi2;eki, "Finding edge-disjoint paths in
partialk-trees," Algorithmica, 26, pp･3-30, 2000･
7. T. Mizuki, H. Shi2;uyaand T. Nishi2;eki, "Sharing secret keys along an Eulerian
circuit,m Electronics and Communications in Japan, Part 3, Vol･83, No･47 pp･33-42, 2000.
8. X. Zhouand T. Nishizeki, "Graph coloring algorithms," IEICETranS･ In f･ & Syst･,
Vbl.E83-D, No.3, pp.407-417, 2000･
9. T. Mizuki, Z.B. Sui and T. Nishizeki, "On the average length of secret key exchange
Eulerian circuits," IEICETranS. Inf. & Syst･, Vol･E83-A, No･4, pp･662-670, 2000･
10. X. Zhou, K. Fuse,and T. Nishizeki "A linearalgorithm for finding 【9, f]-colorings of partialk-trees?n Algorithmica7 27, pp･227-243, 2000･
ll.水木,静谷,西関, "カードの配布による鍵集合プロトコルが最適であるための必要十
分条件,"電子情報通信学会論文誌, Vbl.J38-A, No･5, pp･545-553, 2000･
12. Md. A. Kashem, X. Zhouand T. Nishizeki, "Algorithms for generalized vertex-rankings of partial k-trees,n Theoretical Computer Science, Vol･240, ppAO7-427,
2000.
13. Md. S. Rahman, S. Nakano and T. Nishizeki, "Box-rectangular drawings of plane graphs," Journal of AIgorithms, 37, pp･3631398, 2000･
国際会議等
1. J. Vygen, X. Zhou and T･ Nishizeki, "The edge-disjoint paths problem is
NP-completefor series-parallel graphs," Proc･ of the lst Japanese-Hungarian Sym-posium on Discrete Mathematics and Its Applications, pp･103-110, 1999･
2. T. Mizuki, H. Shizuya and T. Nishizeki, "Dealing necessaryand su氏cient numbers of cards for sharing a one-bit secret key," Proc･ of EUROCRYPT'99, LNCS 1592,
pp.389-401, 1999･
3. K. Miura, S. Nakano and T. Nishizeki, "Grid drawlngS Of four-connected plane graphs,n Proc･ of GD'99, Lect･ Notes in Comp･ Sci･, Springer-verlag, 1731,
pp･145-154,1999･
4. S. Isobe, X. Zhou and T. Nishizeki, "A linear algorithm for finding total colorings
of partial k-trees," Proc･ of ISAAC'99,Lect･ Notes in Comp･ Sci･, Springer-verlag,
1741, pp.347-356, 1999･
5. Y. Kusakari, D. Masubuchi and T･ Nishizeki, "Algorithm for finding noncrosslng
Steiner forests in plane graphs," Proc. of ISSAC'99, Lect･ Notes in Comp･ Sci･,
SpringeトVerlag, 1741, pp･337-346, 1999･
6. Md. S. Rahman, M. Naznin, S. Nakano and T. Nishizeki, "Orthogonaldrawings of biconnected plane graphs without bends," Proc･ oHCCIT'99, pp･199-203, 1999･
7. Md. S. Rahman, S. Nakanoand T. Nishizeki, "Rectangular drawlngS Ofplane graphs
without designated corners," Proc･ of ICCIT'99, pp･244-248, 1999･
8. Md. S. Rahman, S. Nakanoand T. Nishizeki, "Box-rectangular drawings Of plane graphs,¶ Proc･ of Japan-Korea Joint Wわrkshop on Algorithms and Computation,
pp. 72-79, 1999･
9. Md. S. Rahman, S. Nakanoand T. NiShizeki, "Box-rectangular drawlngS Of plane
graphs,M Proc･ ofWG'99, Lect･ Notes in Comp･ Sci･, Springer-Wrlag, 1665,
pp･250-261,1999.
10. T. Mi富uki, Z. Sui, H. Shizuyaand T･ Nishizeki, "On the average length of secret key
exchange Eulerian circuitsTn Proc･ of Japan-Korea Joint Workshop on Algorithms
and Computation, pp･4ト48, 2000･
ll. Md. S. Rahman, S. Nakano and T. Nishizeki, "Rectangular drawings of plane graphs without designated corners,刀 Proc･ of Japan-Korea Joint Workshop on Algorithms
and Computation, pp･130-137, 2000･
12. Md. S. Rahman, S. Nakano and T. Nishizeki, "Rectangular drawlngS Ofplane graphs without designated corners," Proc･ of COCOON 2000, Lect･ Notes in Comp･ Sci･, SpringeトVerlag, 1858, pp･ 85-94, 2000･
13. T. Mizuki, H･ Shizuya and T･ Nishizeki, uCharacterization of optimal key set
pro-tocols,乃Proc･ OHFIP TCS 2000, Lect･ Notes in Comp･ Sci･, SpringeトVerlag, 1872,
pp･ 273- 285) 2000･
14. X. Zhou and T. Nishizeki, uFinding independent spannlng trees in partialk-trees,沖Proc･ of ISAAC 2000,Lect･ Notes in Comp･ Sci･, Springer-verIag, 1969, pp･
168-179, 2000.
15. K. Miura, S･ Nakanoand T･ Nishizeki, uConvex grid drawlngS Of four-connected
plane graphs,乃Proc･ OHSAAC 2000, Lect･ Notes in Comp･ Sci･, Springer-verlag,
目次
1. Y. Kusakari, H･ Suzuki, T･ Nishizeki "A shortest pair of paths on the plane with obstaclesand crosslng areas"
2. X. Zhouand T. Nishizeki, "Edge-coloring and I-coloring for various classes of graphs" 3. S. Isobe, X･ Zhou and T･ Nishizeki, uA polynomial-time algorithm for finding total
colorings of partialk-trees"
4. Md. S. Rahman, S. Nakanoand T. Nishizeki, "A linear algorithm for bend-optimal ortbogonal drawlng8 0f triconnected cubic plane graphsM
5. K. Miura, D. Takahashi, S. Nakanoand T･ Nishizeki, "A linear-timealgorithm to
find four independent spannlng trees in four connected planar graphs"
6. X. Zhou, S. Tamura and T. Nishi2;eki, "Finding edge-disjoint paths in partial
k-trees乃
7. T. Mizuki, H. Shizuya and T. Nishizeki, "Sharing secret keys along an Eulerian
circuit乃
8. X. Zhou and T. Nishizeki, "Graph coloring algorithms"
9. T. Mizuki, Z.B. Suiand T･ Nishizeki,…on the average length of secret key exchange Eulerian circuitsM
10. X. Zhou, K. Fuse,and T. Nishizeki "A linear algorithm for finding 【9, f]-colorings of partialk-trees"
ll.水木,静谷,西関, "カードの配布による鍵集合プロトコルが最適であるための必要十
分条件"
12. Md. A. Kashem, X･ Zhou and T･ Nishizeki, uAlgorithms for generalized
vertex-rankings of partialk-trees"
13. Md. S. RAhman, S. Nakanoand T. Nishizeki, "Box-rectangular drawings of plane graphs乃
TOUR ： Tohoku University Repository コメント・シート 本報告書収録の学術雑誌等発表論文は本ファイルに登録しておりません。なお、このうち東北大学 在籍の研究者の論文で、かつ、出版社等から著作権の許諾が得られた論文は、個別にTOUR に登録 しております。 TOUR http://ir.library.tohoku.ac.jp/
