Hypergraph Cuts with General Splitting Functions
From MaRDI portal
Publication:5094916
DOI10.1137/20M1321048zbMath1494.05080arXiv2001.02817OpenAlexW2999163148MaRDI QIDQ5094916
Nate Veldt, Austin R. Benson, Jon M. Kleinberg
Publication date: 5 August 2022
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.02817
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Core-Periphery Detection in Hypergraphs, What Are Higher-Order Networks?, Comparing the principal eigenvector of a hypergraph and its shadows, Hypergraph analysis based on a compatible tensor product structure
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Realizing symmetric set functions as hypergraph cut capacity
- Minimizing a sum of submodular functions
- The expressive power of binary submodular functions
- A faster strongly polynomial time algorithm for submodular function minimization
- The ellipsoid method and its consequences in combinatorial optimization
- Modeling hypergraphs by graphs with the same mincut properties
- Geometric algorithms and combinatorial optimization.
- Realization of set functions as cut functions of graphs and hypergraphs
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Approximation techniques for hypergraph partitioning problems
- Emerging frontiers in nonlinear science
- Diffuse Interface Models on Graphs for Classification of High Dimensional Data
- Hypergraph Partitioning Based Models and Methods for Exploiting Cache Locality in Sparse Matrix-Vector Multiplication
- Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on Graphs
- Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix Multiplication
- Statistical mechanics of complex networks
- On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe
- Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
- Recent directions in netlist partitioning: a survey
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- A Gomory-Hu cut tree representation of a netlist partitioning problem
- Minimum cuts, modular functions, and matroid polyhedra
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Network Flow and Testing Graph Connectivity
- Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
- The Structure and Function of Complex Networks
- Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
- Cross-linked structure of network evolution
- Multiway cuts in directed and node weighted graphs
- Three Hypergraph Eigenvector Centralities
- Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
- k-way Hypergraph Partitioning via n-Level Recursive Bisection
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Flow-Based Algorithms for Local Graph Clustering
- The complexity of satisfiability problems
- Revisiting Hypergraph Models for Sparse Matrix Partitioning
- Max flows in O(nm) time, or better
- Cutsets and partitions of hypergraphs
- Integer Programming and Combinatorial Optimization
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
