Min-max partitioning of hypergraphs and symmetric submodular functions

DOI10.1007/S00493-023-00021-YMaRDI QIDQ6081377zbMATH OpenOpenAlexFDO

Authors Karthekeyan Chandrasekaran, Chandra Chekuri

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-023-00021-y

zbMATH Keywords

hypergraphspartitioningsubmodular functions

Mathematics Subject Classification ID

Connectivity (05C40) Hypergraphs (05C65) General topics of discrete mathematics in relation to computer science (68R01) General topics in the theory of algorithms (68W01)

Recommendations

• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Minimizing symmetric submodular functions
• Approximating submodular \(k\)-partition via principal partition sequence

Cited in

(5)

• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Approximating submodular \(k\)-partition via principal partition sequence
• Splitting-off in hypergraphs
• Splitting-off in hypergraphs
• Hypergraph connectivity augmentation in strongly polynomial time

This page was built for publication: Min-max partitioning of hypergraphs and symmetric submodular functions

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