Thumbnail
Access Restriction
Open

Author Takaoka, Tadao
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword 2-center Problem ♦ Efficient Algorithm ♦ Conventional Ram Model ♦ Slight Improvement ♦ Unit Edge Cost ♦ Non-negative Edge Cost ♦ Random Accessibility ♦ Known Complexity ♦ Log Log Log ♦ Arithmetic Operation ♦ Directed Graph
Abstract Abstract. This paper achieves O(n 3 log log n / log n) time for the 2-center problems on a directed graph with non-negative edge costs under the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bits are allowed. Here n is the number of vertices. This is a slight improvement on the best known complexity of those problems, which is O(n 3). We further show that when the graph is with unit edge costs, one of the 2-center problems can be solved in O(n 2.575) time. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article