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

Frédéric Maffray (), Nicolas Trotignon () and Kristina Vuskovic ()
Additional contact information
Frédéric Maffray: Laboratoire Leibniz
Nicolas Trotignon: CEntre de Recherche en Mathématiques, Statistique et Economie Mathématique (CERMSEM)
Kristina Vuskovic: University of Leeds

Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1)

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; maximum weight clique algorithm; combinatorial algorithms; perfect graphs; star decompositions (search for similar items in EconPapers)
Pages: 25 pages
Date: 2006-12
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in SIAM Journal on Discrete Mathematics, 2008, 22(1), pp.51–71

Downloads: (external link)
https://halshs.archives-ouvertes.fr/halshs-00130439 (application/pdf)
https://doi.org/10.1137/050628520

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:mse:wpsorb:b06085

Access Statistics for this paper

More papers in Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1) Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().