Algorithms for square-3PC(.,.)-free Berge graphs
AbstractWe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université Panthéon-Sorbonne (Paris 1) in its series Cahiers de la Maison des Sciences Economiques with number b06085.
Length: 25 pages
Date of creation: Dec 2006
Date of revision:
Contact details of provider:
Postal: 106 - 112 boulevard de l'Hôpital, 75647 Paris cedex 13
Phone: 01 44 07 81 00
Fax: 01 44 07 81 09
Web page: http://mse.univ-paris1.fr/
More information through EDIRC
Recognition algorithm; maximum weight clique algorithm; combinatorial algorithms; perfect graphs; star decompositions.;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2007-02-17 (All new papers)
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Lucie Label).
If references are entirely missing, you can add them using this form.