• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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, dans 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
Lien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00017258/en/
Date
2005
Titre du colloque
3rd Asian Applied Computing Conference (AACC 2005)
Date du colloque
2005-12
Ville du colloque
Katmandou
Pays du colloque
Népal
Titre de l'ouvrage
INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005
Auteurs de l’ouvrage
Patnaik, Lalit M.; Talukder, Asoke K.; Bhattarai, Deepak; Jha, Sudan; Pradhan, Hirendra M.; Iyengar, Sitharama
Éditeur
Imperial College Press
Ville d’édition
Londres
Isbn
1-86094-827-8
Nombre de pages
484
Pages
53-57
Métadonnées
Afficher la notice complète
Auteur(s)
Monnot, Jérôme cc
Toulouse, Sophie cc
Résumé (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.
Mots-clés
approximation algorithms; NP-completeness; bipartite graphs; minimum k-path partition; maximum (weighted) Pk-packing; Pk-partition

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Vignette de prévisualisation
    Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2007) Communication / Conférence
  • Vignette de prévisualisation
    The path partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2007) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Complexity and approximation results for bounded-size paths packing problems 
    Toulouse, Sophie; Monnot, Jérôme (2007) Chapitre d'ouvrage
  • Vignette de prévisualisation
    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
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo