CGL Meeting Agenda

Wednesday, September 24th, 1997

Location:
1304
Time:
13:30
Chair:
Celine Latulipe

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:
Rob?
Coffee hour next week:
Volunteer?

3. Next meeting

Date:
October 1st, 1997
Location:
DC 1304
Time:
13:30
Chair:
Marryat Ma
Technical presentation:
Rob Kroeger

4. Forthcoming

Chairs:

  1. Leo Magalhaes (10/8)
  2. Mike Hammond (10/15)
  3. Steve Mann (10/22)
  4. Adarsh Mehta (10/29)

Tech Presenters:

  1. Celine Latulipe (10/8)
  2. Marryat Ma (10/15)
  3. Alberto Raposo (switching with Leo) (10/22)
  4. Mike Hammond (10/29)

5. Technical Presentation

Pete Harwood:
Towards Scene Graph Rewriting
Abstract:
Rendering a scene in computer graphics typically requires the scene to be represented using a data structure such as a tree or a directed acyclic graph. This talk deals with the manipulation of scene graphs by way of Graph Rewriting Systems. Graph Rewriting Systems consist of rules that operate on graphs. In this talk, I will briefly introduce Graph Rewriting Systems and show how they can be used to generate some interesting pictures.

6. General Discussion Items

7. Action List

8. Director's Meeting

9. Seminars

Wednesday, September 24, 1997
Venkatech Raman, The Institute of Mathematical Sciences, 
C.I.T. Campus, Chennai, India,
will speak on "Fixed Parameter Tractability".
TIME: 3:30-4:30 pm
ROOM: DC 1304

ABSTRACT:
Parameterized   complexity   deals  with  computational
problems that have more than one parameter and when one
of  them  is fixed -- for example, problems like VERTEX
COVER (or CLIQUE) where the problem is to find a vertex
cover (or a clique, respectively) of size k in a graph;
here k is the fixed parameter.
The  goal  is to find an algorithm for the problem with
                 c
runtime  O(f(k)*n )  where n is the size of the problem
instance,  f is any (typically exponential) function of
k  and  c  is  a  constant  independent  of k.  Such an
algorithm  is  quite  useful in practice when k is very
small compared to n.  A parameterized problem with such
an  algorithm  is  said to be fixed parameter tractable
(FPT).

In  this  talk,  I will survey some known techniques to
prove  that  a parameterized problem is fixed parameter
tractable.    In   particular   I   will  look  at  the
parameterized  complexity  of  VERTEX  COVER,  FEEDBACK
VERTEX SET, SATISFIABILITY, and MAXCUT.

(Joint  work  with  Rod Downey, Mike Fellows, and Meena
Mahajan.)

10. Lab Cleanup!!!