Affordable Access

Publisher Website

Algorithms for square-$3PC(\cdot, \cdot)$-free Berge graphs

Authors
  • Maffray, Frédéric
  • Trotignon, Nicolas
  • Vušković, Kristina
Type
Published Article
Publication Date
Sep 03, 2013
Submission Date
Sep 03, 2013
Identifiers
DOI: 10.1137/050628520
Source
arXiv
License
Yellow
External links

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(n^{7})$ to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

Report this publication

Statistics

Seen <100 times