On minimizing the maximum congestion for weighted hypergraph embedding in a cycle

DOI10.1016/S0020-0190(03)00297-7zbMath1161.68681MaRDI QIDQ1014437

Hann-Jang Ho, Sing-Ling Lee

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmshypergraphNP-completeLP-relaxationalgorithmical approximation

Mathematics Subject Classification ID

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

Related Items (2)

On packing and coloring hyperedges in a cycle ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring

Cites Work

• Unnamed Item
• Improved approximation algorithms for embedding hyperedges in a cycle
• Algorithms for routing around a rectangle
• Randomized metarounding (extended abstract)
• A linear time algorithm for optimal routing around a rectangle
• Provably good moat routing

This page was built for publication: On minimizing the maximum congestion for weighted hypergraph embedding in a cycle