A contraction algorithm for finding small cycle cutsets

DOI10.1016/0196-6774(88)90013-2MaRDI QIDQ3813312zbMATH OpenOpenAlexFDO

Authors 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 graphminimum cutsetNP-completequasi-reducible graphs

Mathematics Subject Classification ID

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

Recommendations

• Fast computation of small cuts via cycle space sampling
• Efficient Algorithms for the k Smallest Cuts Enumeration
• The complexity of contracting bipartite graphs into small cycles
• A new contraction technique with applications to congruency-constrained cuts
• A new contraction technique with applications to congruency-constrained cuts
• On permuting cut with contraction
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Finding shortest contractible and shortest separating cycles in embedded graphs
• scientific article; zbMATH DE number 7759280

Cited in

(16)

• Distributed revision of composite beliefs
• Algorithms for solving nonlinear dynamic decision models
• Hybrid algorithms with automatic switching for solving nonlinear equation systems
• 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
• Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
• scientific article; zbMATH DE number 4051023 (Why is no real title available?)
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• DETECTION OF SCANS
• Fusion, propagation, and structuring in belief networks
• Superfluous arcs and confluent reductions in the minimum feedback vertex set problem
• Enumerating minimum feedback vertex sets in directed graphs with union-cat trees
• On the confluence of directed graph reductions preserving feedback vertex set minimality
• PACE solver description: hust-solver -- a heuristic algorithm of directed feedback vertex set problem
• PACE solver description: diverses -- a heuristic solver for the directed feedback vertex set problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3813312)