Qustion about minimum (k, n-k)-cut in a graph

From: Joe (Joe.ntang_at_gmail.com)
Date: 03/23/05 

Date: 23 Mar 2005 06:25:33 -0800

Hi,

First I define the minimum (k, n-k)-cut of graph G=(V,E). It is a
partition of V into V' and V-V' with |V'|=k such that the number of
edges across V' and V-V' is minimized.

I cannot find an efficient algorithm for finding a minimum (k,n-k)-cut
in a graph. Can anyone give me some advice ?

Thanks

Joe

Relevant Pages

  • Re: vertices in graph vertex covers
    ... A graph where every vertex is of degree 2 ... a partition shares an edge with another ... Dependent: A variable where the assignment depends on ... For every satisfying assignment where v ...
    (sci.math.research)
  • Constructing Quotient Graphs
    ... If we partition N into k parts. ... We define the "Quotient graph" with respect to the above partition as: ... running time O+size). ...
    (comp.programming)
  • Graph Partitioning Problem
    ... I have an application where I want to find a minimum weight partition ... of an undirected graph into k connected components such that each ... All the graph partitioning algorithms and programs I've seen ... Does anybody know of any algorithms, ...
    (comp.theory)
  • Graph Theory: Cuts, Minimal Cuts and Bonds
    ... These definitions are from Reinhard Diestel's "Graph Theory, ... minimal or maximal sets of vertices or edges, ... We denote the set of this edges in E (edge set of ... partition is called a cut. ...
    (sci.math)
  • Re: combinatorics/graph theory problem for set partitions
    ... >Suppose I construct a random graph by choosing k edges in such a way ... >that each edge is chosen independently with probability p, ... >Then I consider the set partition defined by this graph such that two ...
    (sci.stat.math)