Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach

DOI10.1006/jagm.1996.0047zbMath0861.68034OpenAlexW2051743165MaRDI QIDQ4895807

Subir Roy, H. Narayanan, Sachin B. Patkar

Publication date: 16 October 1996

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1996.0047

zbMATH Keywords

min-\(k\)-cut problemmin-\(k\)-overlap problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (7)

The realization of finite state machines by decomposition and the principal lattice of partitions of a submodular function. ⋮ Improving graph partitions using submodular functions. ⋮ On the \(k\)-cut problem ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Detecting critical nodes in sparse graphs ⋮ A note on optimal covering augmentation for graphic polymatroids.

This page was built for publication: Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach