COE’´ƒƒoƒXƒgŠô‰½ŒvŽZE—ÊŽqŒvŽZ‡“¯ƒZƒ~ƒi[
“úŽžF2006”N6ŒŽ23“úi‹àj@13:30-14:30
êŠFHŠ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™Œ´Œú‹gi“àü‚Q‚U‚X‚O‚Tj |