Mimicking networks for constrained multicuts in hypergraphs

DOI10.4230/LIPICS.ISAAC.2024.21MaRDI QIDQ7260633zbMATH OpenFDO

Authors Kyungjin Cho, Eunjin Oh

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.21

zbMATH Keywords

hyperedge multicutparameterized complexityvertex sparsification

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A parameterized view on matroid optimization problems
• Deterministic truncation of linear matroids
• Exact flow sparsification requires unbounded size
• Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract)
• scientific article; zbMATH DE number 7788412 (Why is no real title available?)
• Matroid theory
• Minimum cuts and sparsification in hypergraphs
• Near-optimal deterministic vertex-failure connectivity oracles
• Near-optimal light spanners
• New notions and constructions of sparsification for graphs and hypergraphs
• On \((1 + \varepsilon)\)-approximate flow sparsifiers
• Parameterized algorithms
• Parameterized graph separation problems
• Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems
• Recent directions in netlist partitioning: a survey
• Representative sets and irrelevant vertices: new tools for kernelization
• Spectral hypergraph sparsifiers of nearly linear size
• The Complexity of Multiterminal Cuts
• The greedy spanner is existentially optimal (extended abstract)
• Vertex sparsification for edge connectivity in polynomial time
• Vertex sparsifiers for hyperedge connectivity

This page was built for publication: Mimicking networks for constrained multicuts in hypergraphs

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