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

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Efficient algorithms for decomposing graphs under degree constraints

Thumbnail
Date
2007
Dewey
Programmation, logiciels, organisation des données
Sujet
Polynomial algorithm; Graph decomposition; Vertex partition; Vertex degree
Journal issue
Discrete Applied Mathematics
Volume
155
Number
8
Publication date
2007
Article pages
979-988
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2006.10.005
URI
https://basepub.dauphine.fr/handle/123456789/1509
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel
Type
Article accepté pour publication ou publié
Abstract (EN)
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

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.