A contraction algorithm for finding small cycle cutsets

DOI10.1016/0196-6774(88)90013-2zbMath0662.68070OpenAlexW1984425270MaRDI QIDQ3813312

Hanoch Levy, David W. Low

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90013-2

zbMATH Keywords

contractiondirected graphNP-completeminimum cutsetquasi-reducible graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items

DETECTION OF SCANS ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Distributed revision of composite beliefs ⋮ Hybrid algorithms with automatic switching for solving nonlinear equation systems ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ Graphical requirements for multistationarity in reaction networks and their verification in BioModels ⋮ Target set selection for conservative populations ⋮ A constraint programming approach to cutset problems ⋮ Fusion, propagation, and structuring in belief networks ⋮ Algorithms for solving nonlinear dynamic decision models

This page was built for publication: A contraction algorithm for finding small cycle cutsets