Format du dépôt |
Fichier |
Type de dépôt |
Autre publication scientifique |
Titre |
en
Algorithms for square-3PC(.,.)-free Berge graphs
|
Résumé |
en
We consider the class of graphs containing no odd hole, no odd antihole and no configuration consisting of three paths between two nodes such that any two of the paths induce a hole and at least two of the paths are of length 2. This class generalizes claw-free Berge graphs and square-free Berge graphs. We give a combinatorial algorithm of complexity O(n7) to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.
fr
Nous considérons la classe des graphes qui ne contiennent ni trou impair, ni antitrou impair, ni configuration consistant en trois chemins arêtes-disjoints, reliant deux sommets, tels que l'union de toute paire de ces chemins induise un trou et tels que deux au moins de ces chemins sont de longueur 2. Cette classe généralise la classe des graphes de Berge sans griffes et la classe des graphes de Berge sans carrés. Nous donnons un algorithme combinatoire de complexité O(n7) pour trouver une clique de poids maximum dans tout graphe de cette classe. Nous étudions aussi quelques problèmes de détection de sous-graphes liés à cette classe.
|
Auteur(s)
|
Frédéric Maffray
1
, Nicolas Trotignon
2
, Kristina Vuskovic
3
1
Leibniz - IMAG -
Laboratoire Leibniz
( 190 )
- 46, avenue Félix Viallet - 38031 GRENOBLE Cedex
- France
-
Université Joseph Fourier - Grenoble 1 ( 51016 )
;
-
Institut National Polytechnique de Grenoble ( 300275 )
;
-
Centre National de la Recherche Scientifique UMR5522 ( 441569 )
2
CES -
Centre d'économie de la Sorbonne
( 15080 )
- Maison des Sciences Économiques - 106-112 Boulevard de l'Hôpital - 75647 Paris Cedex 13
- France
-
Université Paris 1 Panthéon-Sorbonne UMR8174 ( 7550 )
;
-
Centre National de la Recherche Scientifique UMR8174 ( 441569 )
3
School of Computing [Leeds]
( 50523 )
- University of Leeds, Faculty of Engineering, Leeds LS2 9JT
- Royaume-Uni
-
University of Leeds ( 123346 )
|
Langue du document |
Anglais
|
Audience |
Non spécifiée
|
Date de publication |
2006-12
|
Description |
Cahiers de la MSE n°2006.85 - Série Bleue (CERMSEM) - ISSN 1624-0340
|
Nom de la revue |
|
Vulgarisation |
Non
|
Classification |
68 - Computer science/68R - Discrete mathematics in relation to computer science/68R10 - Graph theory (including graph drawing) in computer science
68 - Computer science/68Q - Theory of computing/68Q25 - Analysis of algorithms and problem complexity
05 - Combinatorics/05C - Graph theory/05C85 - Graph algorithms (graph-theoretic aspects)
05 - Combinatorics/05C - Graph theory/05C17 - Perfect graphs
90 - Operations research, mathematical programming/90C - Mathematical programming/90C27 - Combinatorial optimization
|
Commentaire |
Domaine(s) |
-
Sciences de l'Homme et Société/Economies et finances
|
Éditeur scientifique |
-
UMS 1814 Centre de documentation de la Maison des Sciences Economiques
|
Voir aussi |
-
https://doi.org/10.1137/050628520
|
Mots-clés |
en
Recognition algorithm, star decompositions, perfect graphs, combinatorial algorithms, maximum weight clique algorithm
fr
algorithme, graphe parfait, algorithme combinatoire, Algorithme de reconnaissance, décomposition par étoile, clique de taille maximum
|