Recognizing Berge Graphs

Abstract

A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|9). This is independent of the recent proof of the strong perfect graph conjecture.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 20, 2004
Accession Number
AD1021085

Entities

People

  • Gérard Cornuéjols
  • Kristina Vušković
  • Maria Chudnovsky
  • Paul Seymour
  • Xinming Liu

Organizations

  • Princeton University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Construction
  • Decomposition
  • Detectors
  • Mathematics
  • Orientation (Direction)
  • Polynomials
  • Recognition
  • Sequences
  • Specifications
  • Symmetry
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.