NP-hard and linear variants of hypergraph partitioning

DOI10.1016/j.tcs.2009.08.035zbMath1189.68086OpenAlexW1969991812MaRDI QIDQ1041217

Laurent Lyaudet

Publication date: 1 December 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.035

zbMATH Keywords

NP-completenesstransportation problembranchwidthfixed parameter tractablethreshold effectreversalhypergraph partitioningparametrised complexityinversion of complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Structure Detection in Mixed-Integer Programs ⋮ Parallel subgradient algorithm with block dual decomposition for large-scale optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time bounds for selection
• Hypergraph-based parallel computation of passage time densities in large semi-Markov models
• Recent directions in netlist partitioning: a survey
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:4810508 A (1 + ?)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lov�sz Local Lemma]
• Optimal Incremental Sorting
• The complexity of satisfiability problems

This page was built for publication: NP-hard and linear variants of hypergraph partitioning