An Algorithm for a Minimum Cover of a Graph

DOI10.2307/2033599zbMath0093.37702OpenAlexW4250256305MaRDI QIDQ3271425

Michael O. Rabin, Robert Z. Norman

Publication date: 1959

Full work available at URL: https://doi.org/10.2307/2033599

zbMATH Keywords

topology

Related Items

Gallai-Edmonds decomposition as a pruning technique, Nonconvergence, undecidability, and intractability in asymptotic problems, Edge covering problem under hybrid uncertain environments, On strongly connected digraphs with bounded cycle length, Converting triangulations to quadrangulations, Benders decomposition for network design covering problems, The minimal cost maximum matching of a graph, Finding the cyclic covers of a string, Approximation algorithms for a geometric set cover problem, On complementary coverage of \({\Omega}_n(T)\), Boolean functions with long prime implicants, Bounds of graph parameters for global constraints, Covers and packings in a family of sets, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, An efficient algorithm for minimumk-covers in weighted graphs, Dulmage-Mendelsohn canonical decomposition as a generic pruning technique, On complexity of special maximum matchings constructing, Covers, matchings and odd cycles of a graph, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, Sur le nombre transversal des hypergraphes uniformes, Faster Algorithms for Semi-Matching Problems, The distribution of 1-widths of (0,1)-matrices, A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs, Maximum internally stable sets of a graph, Covering numbers of regular multigraphs, Vertex and edge covers with clustering properties: Complexity and algorithms, ``Global graph problems tend to be intractable, Approximation algorithms in combinatorial scientific computing, Fuzzy minimum weight edge covering problem, Generalized edge packings, On the algorithmic complexity of twelve covering and independence parameters of graphs, A note on line coverings of graphs, Equivalence between the minimum covering problem and the maximum matching problem

Cites Work

• Algebraic Topological Methods for the Synthesis of Switching Systems. I
• TWO THEOREMS IN GRAPH THEORY