第314回研究講演会開催案内
情報処理学会東北支部講演会
共催:東北大学電気情報系コンピュータサイエンス研究会
下記の通り講演会を開催いたしますので、ご自由に聴講ください。
日時:2005年2月9日(水)15:00−16:00
会場:東北大学工学部電気情報系2号館4階403号室
題目:
Subexponential-time framework for optimal embeddings of graphs in integer lattices
講演者
Professor Andrzej Lingas
Department of Computer Science
Lund University
Sweden
BSTRACT:
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 bounds
in 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.
問い合わせ先:西関隆夫