Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: VJM banner 

 

Home

 

Recent Issues

Volume 47

1

2

3

 

Volume 46

1

2

3

4

Volume 45

1&2

3

4

Volume 44

1

2

3

4

Volume 43

1

2

3

4

Past Issues

The Journal

Cover

Aims and Scope

Subscription Information

Editorial Board

Instructions for Author

Contact Us

 

 

 

Vietnam Journal of Mathematics 36:3(2008) 327-336

Performance Analysis of Greedy Algorithms for Max-IS and Min-Maxl-Match 

Le Cong Thanh

Abstract.  We consider the approximating behaviour of greedy algorithms, in terms of performance ratios, for the maximum independent set and minimum maximal matching problems, two classical NP-hard problems. The main results tend to confirm our observation that the performance of algorithms in almost every-case is generally much better than worst-case performance. In particular, we show that for almost every instance of the minimum maximal matching problem the greedy algorithm finds a feasible solution that is near-optimal.

 

2000 Mathematics Subject Classification: 68Q17.

Keywords: Independent set, matching, greedy algorithm, performance ratio.

 

 

 

 

 

 

 

 

 

Established by Vietnam Academy of Science and Technology & Vietnam Mathematical Society

Published by Springer since January 2013