Exercises
Multiple Choice
Articles
Open Problems
Login
5 exercises
Tagged:
vertex cover
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Graduate
By
Shiva Kintali
on June 17, 2012 | Updated Dec. 6, 2017
Vertex cover using DFS
Consider the following algorithm for Vertex Cover of a graph \(G\) : Run depth first search (DFS) on \(G\). Output the vertices which are not leaves in the DFS tree. Prove the following : The ou…
Computer Science
Mathematics
Approximation Algorithms
Graph Theory
vertex cover
0
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Dec. 6, 2017
Gallai Identities
Consider the following parameters of an undirected graph \(G\) on \(n\) vertices. \(\nu(G)\) is the size of a maximum matching of \(G\). \(\tau(G)\) is the size of a minimum vertex cover of \(G\). …
Mathematics
Graph Theory
edge cover
independent set
matching
vertex cover
0
Undergraduate
By
Shiva Kintali
on June 8, 2012 | Updated Dec. 6, 2017
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 optimal vertex cover in \(T\). Find a maximum matching in \(T\). Find a maximum i…
Computer Science
Mathematics
Algorithms
Graph Theory
independent set
linear time algorithms
matching
trees
vertex cover
0
Graduate
By
Shiva Kintali
on Sept. 11, 2012 | Updated Dec. 6, 2017
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 to at least one vertex of the set \(S\). Minimum cost vertex cover : Given a…
Mathematics
Optimization
Graph Theory
Linear Programming
bipartite graph
vertex cover
0
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Dec. 6, 2017
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 end point in \(V\). Design an \(O(|V|{\cdot}k + k^2{2^k})\) time algorithm t…
Computer Science
Algorithms
fpt algorithms
vertex cover
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
extremal graph theory
graph cut
spanning tree
trees
fibonacci
induction
tiling
asymptotic analysis
volume
circle
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×