• Exercises
  • Multiple Choice
  • Articles
  • Open Problems
  • Login
3 exercises
Tagged:
  • reduction x

Start over - to expand, or dig in by adding more tags and revising the query.

Sort By: trending ▼ date
0
Undergraduate
By John Doe on Nov. 3, 2012 | Updated Dec. 6, 2017

Direct reduction from Graph Homomorphism to SAT

The decision problem \(GraphHomo\) is defined as follows: \(GraphHomo = \{\langle G, H\rangle \mid \text{there is a graph homomorphism from G to H}\}\) Give a direct reduction from \(GraphHomo\) to …
  • Computer Science
  • Mathematics
  • Complexity Theory
  • Graph Theory
  • Logic
  • np
  • reduction
  • sat
0
Undergraduate
By Shiva Kintali on June 12, 2012 | Updated Dec. 6, 2017

Subset Sum vs Partition

Consider the following problems : Partition problem : Given a collection of \(n\) integers \(a_1, a_2, \ldots, a_n\), is there a subset \(I~\subset~{1,2, \ldots, n }\) such that …
  • Computer Science
  • Algorithms
  • NP completeness
  • partition
  • reduction
  • subset sum
0
Graduate
By Shiva Kintali on June 9, 2012 | Updated Dec. 6, 2017

Minimum edge cover vs Maximum matching

An edge cover of a graph \(G(V,E)\) is a subset \(F \subseteq E\) of edges such that every node is incident to at least one edge in \(F\). Show that a minimum cardinality edge cover can be determine…
  • Mathematics
  • Optimization
  • Graph Theory
  • Linear Programming
  • edge cover
  • matching
  • reduction
  • 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

  • differentiation
  • inequality
  • jee
  • jee 2016
  • jee advanced
  • jee mathematics
  • jee main
  • statistics
  • variance
  • equation

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
Home
Team Terms of Service Privacy Policy Careers Contact Us
Tags Topics IIT JEE Problems International Mathematical Olympiad
Twitter Instagram Slack Telegram
Social learning platform. © 2016 True Group Inc. All Right Reserved