Art

J-GLOBAL ID：201702278966841913   Reference number：17A0777169

An Efficient Approximate Algorithm for the 1-Median Problem on a Graph

グラフにおける1メジアン問題の効率的近似アルゴリズム

Author (3)： TABATA Koji (Graduate School of Information Science and Technology, Hokkaido University) ,  NAKAMURA Atsuyoshi (Graduate School of Information Science and Technology, Hokkaido University) ,  KUDO Mineichi (Graduate School of Information Science and Technology, Hokkaido University)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E100.D  Issue： 5  Page： 994-1002(J-STAGE)  Publication year： 2017 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 短報  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *graph ,  *median value ,  *computer algorithm ,  algorithm ,  network ,  spanning tree ,  subgraph ,  knowledge acquisition
Semi thesaurus term： *median ,  *approximate algorithm ,  heuristic algorithm ,  subgraph ,  graph mining

Author keywords (3)： 1-median problem ,  closeness centrality ,  graph mining

JST classification (2)： Theory of computation  (JB02000A) ,  Basics of graph theory  (IA02020S)

Reference (15)：

• [1] O. Alp, E. Erkut, and Z. Drezner, “An efficient genetic algorithm for the p-median problem,” Annals of Operations research, vol.122(1-4), pp.21-42, 2003.
• [2] R.E. Burkard and J. Krarup, “A linear algorithm for the pos/neg-weighted 1-median problem on a cactus,” Computing, vol.60, no.3, pp.193-215, 1998.
• [3] M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM (JACM), vol.34, no.3, pp.596-615, 1987.
• [4] L.C. Freeman, “Centrality in social networks conceptual clarification,” Social networks, vol.1, no.3, pp.215-239, 1978.
• [5] A.J. Goldman, “Optimal center location in simple networks,” Transportation science, vol.5, no.2, pp.212-221, 1971.

Terms in the title (4)： グラフ ,  メジアン ,  問題 ,  近似アルゴリズム