Home
학과소식
세미나
기존 세미나
기존 세미나
[해양기술 인력양성사업단] Closed colorings: a conjecture and its implications
[해양기술 인력양성사업단 세미나]
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)
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)
첨부파일 (1개)
- 해양기술사업단세미나공고문(2010.07.15)-홍성필(Refael Hassin).pdf (141 KB, download:111)