𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear time algorithm for graph partition problems

✍ Scribed by L.H. Clark; F. Shahrokhi; L.A. Székely

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
483 KB
Volume
42
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Algorithms for the minimum partitioning
Algorithms for the minimum partitioning problems in graphs
✍ Hiroshi Nagamochi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 545 KB

## Abstract In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non‐negative weights for edges is divided into __k__ subsets, the set of edges for which both endpoints are contained in differen

Approximation Algorithms for Maximizatio
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
✍ Uriel Feige; Michael Langberg 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 261 KB

Given a graph G = V E , a weight function w E → R + , and a parameter k, we consider the problem of finding a subset U ⊆ V of size k that maximizes: Max-Vertex Cover k the weight of edges incident with vertices in U, Max-Dense Subgraph k the weight of edges in the subgraph induced by U, Max-Cut k th