Improving graph partitions using submodular functions.

DOI10.1016/S0166-218X(02)00472-9MaRDI QIDQ1410700zbMATH OpenOpenAlexFDO

Authors Sachin Patkar, H. Narayanan

Publication date 14 October 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(02)00472-9

zbMATH Keywords

VLSI design automation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Algorithms and lower bounds for submodular cuts and approximating submodular functions
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• scientific article; zbMATH DE number 1982182
• Min-cut partitioning on underlying tree and graph structures

Cites work

• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 2080194 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A faster algorithm for computing the strength of a network
• A new approach to the maximum-flow problem
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach
• Computing the Strength of a Graph
• Greedily Finding a Dense Subgraph
• On Nonlinear Fractional Programming
• Selected Applications of Minimum Cuts in Networks
• Spectral partitioning with multiple eigenvectors
• Submodular functions and electrical networks
• Submodular functions and optimization

Cited in

(3)

• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Theory of principal partitions revisited
• Approximating submodular \(k\)-partition via principal partition sequence

This page was built for publication: Improving graph partitions using submodular functions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1410700)