Problem
Consider a graph G = (V, E), where V denotes the set of n vertices and E the set of edges. For a (k,v) balanced partition problem, the objective is to partition G into k components of at most size vยท(n/k), while minimizing the capacity of the edges between separate components. Also, given G and an integer k > 1, partition V into k parts (subsets) V1, V2, ..., Vk such that the parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. Such partition problems have been discussed in literature as bicriteria-approximation or resource augmentation approaches. A common extension is to hypergraphs, where an edge can connect more than two vertices. A hyperedge is not cut if all vertices are in one partition, and cut exactly once otherwise, no matter how many vertices are on each side. This usage is common in electronic design automation.
Read more about this topic: Graph Partition
Famous quotes containing the word problem:
“The problem of induction is not a problem of demonstration but a problem of defining the difference between valid and invalid
predictions.”
—Nelson Goodman (1906)
“In the nineteenth century the problem was that God is dead; in the twentieth century the problem is that man is dead.”
—Erich Fromm (1900–1980)
“To make a good salad is to be a brilliant diplomatist—the problem is entirely the same in both cases. To know exactly how much oil one must put with one’s vinegar.”
—Oscar Wilde (1854–1900)