21¢‹ICOEuî•ñ‰ÈŠw‹Zpí—ªƒRƒAv


COE’´ƒƒoƒXƒgŠô‰½ŒvŽZE—ÊŽqŒvŽZ‡“¯ƒZƒ~ƒi[

“úŽžF2006”N6ŒŽ23“úi‹àj@13:30-14:30
êŠFHŠw•”‚P‚S†ŠÙ‚UŠKŒv”‘åƒZƒ~ƒi[Žºi‚U‚Q‚U†Žºj
u‰‰ŽÒFDavid Avis iƒJƒiƒ_Eƒ}ƒMƒ‹‘åŠw‹³Žöj


ŠT—v

u‰‰ŽÒFDavid Avis iƒJƒiƒ_Eƒ}ƒMƒ‹‘åŠw‹³Žöj

Title: Geometric Enumeration Problems

Abstract:
In this talk we review the reverse search method for generating large sets of discrete objects. An easy use of reverse search is to generate all bases of a matroid, such as spanning trees of a graph. We will then combine reverse search with some properties of matroids to give a method for generating objects, which do not form a matroid, but are closely related to one. As an example, we can generate efficiently all planar Laman graphs drawn on a given set of points in the plane. (Joint work with N. Katoh, M. Ohsaki, I. Streinu and S. Tanigawa)

˜A—æF™Œ´Œú‹gi“àü‚Q‚U‚X‚O‚Tj


ŽÀs‘gDƒvƒƒWƒFƒNƒgŠT—vƒvƒƒWƒFƒNƒgÚ×ŽóÜ‚̏Љî‰ï‹cEŠÖ˜AsŽ–What's New—š—ð‚¨–â‚¢‡‚¹
iCj Copyright 2006 Information Science and Technology Strategic Core All Rights Reserved.