On approximating the maximum diameter ratio of graphs

被引：11
作者：
Marincek, J [1 ]
Mohar, B [1 ]
机构：
[1] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia
来源：
DISCRETE MATHEMATICS | 2002年 / 244卷 / 1-3期
关键词：
approximation algorithm; APX-complete problem; local density; diameter;
D O I：
10.1016/S0012-365X(01)00091-7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 is proved to be even harder to approximate. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：323 / 330
页数：8
相关论文
共 9 条
1