1.5.6 Graph Partition

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A (weighted) graph G=(V,E) . Integers j , k , and m .

Problem: Partition the vertices into m subsets such that each subset has size at most j , while the cost of the edges spanning subsets is bounded by k .

Implementations

  • LINK -- Programming and Visualization Environment for Hypergraphs (C++) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 4)

    Related Problems

  • Edge and Vertex Connectivity
  • Graph Data Structures
  • Network Flow
  • Planarity Detection and Embedding

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .