A linear-time algorithm for computing the intersection of all odd cycles in a graph

Leizhen Cai, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We present a linear-time algorithm that finds all edges and vertices in the intersection of all odd cycles in a given graph. We also show an application of our algorithm to a variant of the satisfiability problem of Boolean formulas.

Original languageEnglish (US)
Pages (from-to)27-34
Number of pages8
JournalDiscrete Applied Mathematics
Volume73
Issue number1
DOIs
StatePublished - Feb 21 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Bipartite graph
  • Graph algorithm
  • Odd cycle
  • Satisfiability problem

Fingerprint

Dive into the research topics of 'A linear-time algorithm for computing the intersection of all odd cycles in a graph'. Together they form a unique fingerprint.

Cite this