• 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 - Request a copy

Complexity of two coloring problems in cubic planar bipartite mixed graphs

Ries, Bernard (2010), Complexity of two coloring problems in cubic planar bipartite mixed graphs, Discrete Applied Mathematics, 158, 5, p. 592-596. http://dx.doi.org/10.1016/j.dam.2009.10.016

Type
Article accepté pour publication ou publié
Date
2010
Nom de la revue
Discrete Applied Mathematics
Volume
158
Numéro
5
Éditeur
Elsevier
Pages
592-596
Identifiant publication
http://dx.doi.org/10.1016/j.dam.2009.10.016
Métadonnées
Afficher la notice complète
Auteur(s)
Ries, Bernard
Résumé (EN)
In this note we consider previous termtwo coloring problemsnext term in previous termmixed graphs, i.e., graphsnext term containing edges and arcs, which arise from scheduling previous termproblemsnext term where disjunctive and precedence constraints have to be taken into account. We show that they are both View the MathML source-complete in previous termcubic planar bipartite mixed graphs,next term which strengthens some results of Ries and de Werra (2008) [9].
Mots-clés
Mixed graph coloring; List coloring; Bipartite graph; Scheduling; Computational complexity

Publications associées

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

  • Vignette de prévisualisation
    On the complexity of the selective graph coloring problem in some special classes of graphs 
    Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Weighted coloring on planar, bipartite and split graphs: complexity and approximation 
    Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation 
    de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
  • Vignette de prévisualisation
    Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term 
    Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    d-Transversals of stable sets and vertex covers in weighted bipartite graphs 
    Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
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