Algorithms for square-3PC(.,.)-free Berge graphs

Frédéric Maffray (), Nicolas Trotignon () and Kristina Vuskovic ()
Additional contact information
Frédéric Maffray: Leibniz - IMAG - Laboratoire Leibniz - UJF - Université Joseph Fourier - Grenoble 1 - INPG - Institut National Polytechnique de Grenoble - CNRS - Centre National de la Recherche Scientifique
Nicolas Trotignon: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Kristina Vuskovic: School of Computing [Leeds] - University of Leeds

Post-Print from HAL

Abstract: 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.

Keywords: Recognition algorithm; star decompositions; perfect graphs; combinatorial algorithms; maximum weight clique algorithm; algorithme; graphe parfait; algorithme combinatoire; Algorithme de reconnaissance; décomposition par étoile; clique de taille maximum (search for similar items in EconPapers)
Date: 2006-12
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00130439v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 2006

Downloads: (external link)
https://shs.hal.science/halshs-00130439v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00130439

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().