Maximum dispersion problem in dense graphs

被引：10

作者：

Czygrinow, A ^{[1
]}

机构：

[1] Arizona State Univ, Dept Math, Tempe, AZ 85287 USA

来源：

OPERATIONS RESEARCH LETTERS | 2000年 / 27卷 / 05期

关键词：

dispersion problem; algorithm; regularity lemma;

D O I：

10.1016/S0167-6377(00)00058-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this note, we present a polynomial-time approximation scheme for a "dense case" of dispersion problem in weighted graphs, where weights on edges are integers from (1,...,K) for some fixed integer K. The algorithm is based on the algorithmic version the regularity lemma. (C) 2000 Published by Elsevier Science B.V. Ali rights reserved.

引用

收藏

页码：223 / 227

页数：5

相关论文

共 11 条

[1] THE ALGORITHMIC ASPECTS OF THE REGULARITY LEMMA [J].

ALON, N ;

DUKE, RA ;

LEFMANN, H ;

RODL, V ;

YUSTER, R .

JOURNAL OF ALGORITHMS, 1994, 16 (01) :80-109

[2]

Arora S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P284, DOI 10.1145/225058.225140

[3] Constructive quasi-Ramsey numbers and tournament ranking [J].

Czygrinow, A ;

Poljak, S ;

Rödl, V .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (01) :48-63

[4] A FAST APPROXIMATION ALGORITHM FOR COMPUTING THE FREQUENCIES OF SUBGRAPHS IN A GIVEN GRAPH [J].

DUKE, RA ;

LEFMANN, H ;

RODL, V .

SIAM JOURNAL ON COMPUTING, 1995, 24 (03) :598-620

[5]

EIGE U, 1999, UNPUB DENSE K SUBGRA

[6] The regularity Lemma and approximation schemes for dense problems [J].

Frieze, A ;

Kannan, R .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :12-20

[7] Approximation algorithms for maximum dispersion [J].

Hassin, R ;

Rubinstein, S ;

Tamir, A .

OPERATIONS RESEARCH LETTERS, 1997, 21 (03) :133-137

[8]

Komlos J, 1996, BOLYAI MATH STUD, V2, P295

[9]

Kortsarz G., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P692, DOI 10.1109/SFCS.1993.366818

[10] HEURISTIC AND SPECIAL CASE ALGORITHMS FOR DISPERSION PROBLEMS [J].

RAVI, SS ;

ROSENKRANTZ, DJ ;

TAYI, GK .

OPERATIONS RESEARCH, 1994, 42 (02) :299-310