The complexity of the Pk partition problem and related problems in bipartite graphs

Monnot, Jérôme; Toulouse, Sophie

Monnot, Jérôme; Toulouse, Sophie (2005), The complexity of the Pk partition problem and related problems in bipartite graphs, in Patnaik, Lalit M.; Talukder, Asoke K.; Bhattarai, Deepak; Jha, Sudan; Pradhan, Hirendra M.; Iyengar, Sitharama, INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005, Imperial College Press : Londres, p. 53-57

Type

Communication / Conférence

External document link

http://hal.archives-ouvertes.fr/hal-00017258/en/

Date

2005

Conference title

3rd Asian Applied Computing Conference (AACC 2005)

Conference date

2005-12

Conference city

Katmandou

Conference country

Népal

Book title

INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005

Book author

Patnaik, Lalit M.; Talukder, Asoke K.; Bhattarai, Deepak; Jha, Sudan; Pradhan, Hirendra M.; Iyengar, Sitharama

Publisher

Imperial College Press

Published in

Londres

ISBN

1-86094-827-8

Number of pages

484

Pages

53-57

Metadata

Show full item record

Author(s)

Monnot, Jérôme

Toulouse, Sophie

Abstract (EN)

In this paper, we continue the investigation made in [MT05] about the approximability of Pk partition problems, but focusing here on their complexity. Precisely, we aim at designing the frontier between polynomial and NP-complete versions of the Pk partition problem in bipartite graphs, according to both the constant k and the maximum degree of the input graph. We actually extend the obtained results to more general classes of problems, namely, the minimum k-path partition problem and the maximum Pk packing problem. Moreover, we propose some simple approximation algorithms for those problems.

Subjects / Keywords

approximation algorithms; NP-completeness; bipartite graphs; minimum k-path partition; maximum (weighted) Pk-packing; Pk-partition