• 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

Decomposition of graphs: some polynomial cases

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003), Decomposition of graphs: some polynomial cases. https://basepub.dauphine.fr/handle/123456789/3938

View/Open
notedeR35.pdf (242.0Kb)
Type
Document de travail / Working paper
Date
2003
Series title
Note de recherche du LAMSADE
Pages
11
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel
Abstract (EN)
We study the problem of decomposing the vertex set V of a graphinto two parts (V1, V2) which induce subgraphs where each vertex vin V1 has degree at least a(v) and each vertex v in V2 has degreeat least b(v). We investigate several polynomial cases of this NP-complete problem. We give a polynomial-time algorithm for graphswith bounded treewidth which decides if a graph admits a decom-position and gives such a decomposition if it exists. We also givepolynomial-time algorithms that always find a decomposition for thefollowing two cases : triangle-free graphs such that d(v) ≥ a(v) + b(v)for all v ∈ V and graphs with girth at least 5 such that d(v) ≥a(v) + b(v) − 1 for all v ∈ V .
Subjects / Keywords
Polynomial Algorithm; treewidth; girth; Graph; Decomposition; Complexity; degree constraints

Related items

Showing items related by title and author.

  • Thumbnail
    Degree-constrained decompositions of graphs: bounded treewidth and planarity 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2006) Article accepté pour publication ou publié
  • Thumbnail
    On the existence and determination of satisfactory partitions in a graph 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) Communication / Conférence
  • Thumbnail
    Efficient algorithms for decomposing graphs under degree constraints 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
  • Thumbnail
    Satisfactory graph partition, variants, and generalizations 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of the satisfactory partition problem 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) 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