graphs.greedy_min_vertex_cover

  • Author: Manuel Di Lullo (https://github.com/manueldilullo)

  • Description: Approximization algorithm for minimum vertex cover problem.

    Greedy Approach. Uses graphs represented with an adjacency list

URL: https://mathworld.wolfram.com/MinimumVertexCover.html URL: https://cs.stackexchange.com/questions/129017/greedy-algorithm-for-vertex-cover

Attributes

graph

Functions

greedy_min_vertex_cover(→ set[int])

Greedy APX Algorithm for min Vertex Cover

Module Contents

graphs.greedy_min_vertex_cover.greedy_min_vertex_cover(graph: dict) → set[int]

Greedy APX Algorithm for min Vertex Cover @input: graph (graph stored in an adjacency list where each vertex

is represented with an integer)

@example: >>> graph = {0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]} >>> greedy_min_vertex_cover(graph) {0, 1, 2, 4}

graphs.greedy_min_vertex_cover.graph