Tuesday, January 11

Session 9A

9:00 AM-10:40 AM
Room: Gold Rush A

9:00 Coloring Powers of Planar Graphs

Geir Agnarsson and Magnús M. Halldórsson, University of Iceland, Iceland

9:25 Directed Network Design with Orientation Constraints

Sanjeev Khanna, Joseph (Seffi) Naor, and F. Bruce Shepherd, Bell Laboratories, Lucent Technologies

9:50 A (2 + e)-Approximation Scheme for Minimum Domination on Circle Graphs

Mirela Damian-Iordache, University of Iowa; and Sriram V. Pemmaraju, Indian Institute of Technology-Bombay, India

10:15 An Approximation Algorithm for Finding a Long Path in Hamiltonian Graphs

Sundar Vishwanathan, Indian Institute of Technology-Bombay, India