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

Leizhen Cai; Baruch Schieber

doi:10.1016/S0166-218X(96)00074-1

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

Leizhen Cai, Baruch Schieber

Research output: Contribution to journal › Article › peer-review

7 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 language	English (US)
Pages (from-to)	27-34
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	73
Issue number	1
DOIs	https://doi.org/10.1016/S0166-218X(96)00074-1
State	Published - Feb 21 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Bipartite graph
Graph algorithm
Odd cycle
Satisfiability problem

Access to Document

10.1016/S0166-218X(96)00074-1

Cite this

@article{eca15eb30dc34481912be2dabb6a9819,

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

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.",

keywords = "Bipartite graph, Graph algorithm, Odd cycle, Satisfiability problem",

author = "Leizhen Cai and Baruch Schieber",

note = "Funding Information: The first author was partially supportedb y an Earmarked Grant from the Research Grants Council of Hong Kong and a Direct Grant for Research from the Chinese University of Hong Kong.",

year = "1997",

month = feb,

day = "21",

doi = "10.1016/S0166-218X(96)00074-1",

language = "English (US)",

volume = "73",

pages = "27--34",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

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

AU - Cai, Leizhen

AU - Schieber, Baruch

N1 - Funding Information: The first author was partially supportedb y an Earmarked Grant from the Research Grants Council of Hong Kong and a Direct Grant for Research from the Chinese University of Hong Kong.

PY - 1997/2/21

Y1 - 1997/2/21

N2 - 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.

AB - 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.

KW - Bipartite graph

KW - Graph algorithm

KW - Odd cycle

KW - Satisfiability problem

UR - http://www.scopus.com/inward/record.url?scp=0041875855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041875855&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(96)00074-1

DO - 10.1016/S0166-218X(96)00074-1

M3 - Article

AN - SCOPUS:0041875855

SN - 0166-218X

VL - 73

SP - 27

EP - 34

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this