• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Efficient algorithms for decomposing graphs under degree constraints

Thumbnail
Date
2007
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Polynomial algorithm; Graph decomposition; Vertex partition; Vertex degree
Nom de la revue
Discrete Applied Mathematics
Volume
155
Numéro
8
Date de publication
2007
Pages article
979-988
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2006.10.005
URI
https://basepub.dauphine.fr/handle/123456789/1509
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel
Type
Article accepté pour publication ou publié
Résumé en anglais
Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321–324] proved that if every vertex v in a graph G has degree d(v)greater-or-equal, slanteda(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that dA(v)greater-or-equal, slanteda(v) for every vset membership, variantA and dB(v)greater-or-equal, slantedb(v) for every vset membership, variantB. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7–9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237–239] strengthened this result, proving that it suffices to assume d(v)greater-or-equal, slanteda+b (a,bgreater-or-equal, slanted1) or just d(v)greater-or-equal, slanteda+b-1 (a,bgreater-or-equal, slanted2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.