A linear-time algorithm for computing the intersection of all odd cycles in a graph
type: Item
instance of: scholarly article
title: A linear-time algorithm for computing the intersection of all odd cycles in a graph
zbMATH Open document ID: 0867.05066
DOI: 10.1016/S0166-218X(96)00074-1
author: Leizhen Cai
author: Baruch Schieber
published in: Discrete Applied Mathematics
publication date: 1997-08-03T00:00:00Z
full work available at URL: dam
review text: The authors consider the problem of finding edges and vertices in a graph \(G\) that are contained in every odd cycle of \(G\). This problem is partially motivated by a fixed-parameter version of two well-known NP-complete problems. A characterization of the intersection of all odd cycles in a graph \(G\) is proposed by using the intersection of the \(T\)-spans of all monochromatic edges (\(T\) is a spanning tree of \(G\)) and the partial subgraph of \(G\) obtained by removing all monochromatic edges. Using this result, a linear-time algorithm is then exhibited. An application of this algorithm is given to a satisfiability problem, namely the minimum mono-valued 2SAT.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 987766
zbMATH Keywords: odd cycle
zbMATH Keywords: linear-time algorithm
zbMATH Keywords: satisfiability
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q4065051
cites work: Q5422499
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q4142699
cites work: The complexity of satisfiability problems
description: scientific article; zbMATH DE number 987766