第314回研究講演会開催報告
- 情報処理学会東北支部特別講演会報告
- 日時：2005年2月9日（水）15：00−16：00
- 場所：東北大学大学院情報科学研究科 電気情報系2号館403号室
- 演題：Subexponential-time framework for optimal embeddings of graphs in integer lattices
- 講師：Professor Andrzej Lingas
- Department of Computer Science，Lund University Sweden
- 概要：
We present a general framework for computing various optimal embeddings of
undirected and directed connected graphs in two and multi-dimensional integer
lattices in time sub-exponential either in the minimum number n of lattice points
used by such optimal embeddings or in the budget upper bound b on the number of
lattice points that may be used in an embedding.
For the problem of minimum total edge length planar or multi-dimensional embedding
or layout of a graph and the problem of an optimal protein folding in the so called
HP model we obtain the upper boundsin terms of n. Note that in case of protein
folding n is also the size of the input.
The list of problems for which we can derive the upper bounds in terms of
b includes among other things:
- a minimum area planar embedding or layout of a graph,
- a minimum bend planar or three dimensional embedding or layout,
- a minimum maximum edge length planar or three dimensional embedding or layout.
This is a joint work with Anders Dessmark and Eva−Marta Lundell.
- 講演報告：
講演後は多数の質問が寄せられ，活発な質疑応答が行われた．
講師のLingas教授からの回答に加えて参加者の方からも貴重なコメントを頂くなど，
大変充実した内容であった．
-
- 参加者：約30名
- 報告者：西関 隆夫
- 東北大学 大学院情報科学研究科
- 〒980-8579 仙台市青葉区荒巻字青葉6-6-05
- TEL: 022-217-7162 FAX: 022-263-9301