When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

physicsIE's blog

By physicsIE, history, 5 years ago, In English

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

A minimum vertex cover is a vertex cover with minimal cardinality.

Consider a set of all minimum vertex covers of a given bipartite graph.

our task is to divide all the vertices of the graph into three sets.

A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.

A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.

If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

How to classify vertices?

Basically, I want to solve this problem

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?