Cookie Setting MathNet Korea

이전페이지 이동
Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
[2017 Discrete Math 세미나]
Date: 2017-09-26
Speaker : Sergio Cabello (University of Ljubljana, Ljubljana, Slovenia)
Abstract : We show how to compute for n-vertex planar graphs in roughly O(n^(11/6)) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(n^c) for some constant c<2, even when restricted to undirected, unweighted planar graphs.
VOD : [Android_VOD]    [iPhone_VOD]    [Windows_VOD]
PC버전
Information Center for Mathematical Sciences KAIST
305-701 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8195~6 / 팩스 042-350-5722
e-mail : mathnet@mathnet.or.kr
Copyright (C) 2017. ICMS All Rights Reserved.