• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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

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 cc
Toulouse, Sophie cc
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

Related items

Showing items related by title and author.

  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Thumbnail
    Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2007) Communication / Conférence
  • Thumbnail
    The path partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2007) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for bounded-size paths packing problems 
    Toulouse, Sophie; Monnot, Jérôme (2007) Chapitre d'ouvrage
  • Thumbnail
    A matching-related property of bipartite graphs with applications in signal processing 
    Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; Rios-Solis, Yasmin Agueda (2009) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo