[해양기술 인력양성사업단 세미나]

1. 제 목 : Closed colorings: a conjecture and its implications

2. 연 사 : Prof. Refael Hassin (Tel Aviv University)

3. 내용 :
We define closed edge colorings of directed graphs, and state a conjecture about the maximum size of a tournament graph that can be arc colored with m colors and contain no closed subgraphs. We show that if this conjecture is correct then for any (undirected) graph with positive edge lengths and a given subset V’ of nodes, covering all the shortest paths between pairs of nodes of V’ requires at least |V’| - 1 edges. We use the latter property to improve a result of Li, McCormick, and Simchi-Levi (1992) about approximating the diameter or the radius of an unweighted graph by adding to it a given number of new edges.

4. 일 시 : 2010년 7월 15일(목) 오전 10:30~12:00

5. 장 소 : 39동 309호(세미나실)

6. 문 의 : 산업 조선공학부 홍성필 교수 (880-1477 / sphong@snu.ac.kr)