5 exercises

Search tips: start over - to expand, or dig in by adding more tags and revising the query.

116

views

no

votes

Vertex cover in bipartite graphs

The Vertex Cover of a graph $G(V,E)$ is a set of vertices $S \subseteq V$ such that each edge of the graph is incident t…

• GRAPH THEORY
• LINEAR PROGRAMMING

 

• vertex-cover
• bipartite-graph

106

views

1

vote

Gallai Identities

Consider the following parameters of an undirected graph $G$ on $n$ vertices. $\nu(G)$ is the size of a maximum matchi…

• GRAPH THEORY

 

• matching
• vertex-cover
• edge-cover
• independent-set

163

views

5

votes

Vertex cover using DFS

Consider the following algorithm for Vertex Cover of a graph $G$ : Run depth first search (DFS) on $G$. Output the ver…

• APPROXIMATION ALGORITHMS
• GRAPH THEORY

 

• vertex-cover

62

views

1

vote

Linear time algorithms on trees

Let $T(V,E)$ be a tree. Design linear time (i.e., $O(|V|)$ time) algorithms for the following problems : Find an optim…

• ALGORITHMS
• GRAPH THEORY

 

• linear-time-algorith...
• trees
• vertex-cover
• matching
• independent-set

24

views

no

votes

Fixed-parameter tractability of Vertex Cover

Let $G(V,E)$ be an undirected graph. A subset $S \subseteq V$ is a vertex cover of $G$ if every edge has at least one en…

• ALGORITHMS

 

• fpt-algorithms
• vertex-cover