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

DOI10.1016/S0020-0190(03)00297-7MaRDI QIDQ1014437zbMATH OpenFDO

Authors Hann-Jang Ho, Sing-Ling Lee

Publication date 28 April 2009

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

Full work available at URL https://doi.org/10.1016/S0020-0190(03)00297-7

zbMATH Keywords

algorithmical approximationalgorithmshypergraphLP-relaxationNP-complete

Mathematics Subject Classification ID

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

Recommendations

• Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle
• A 2-approximation algorithm for an embedded hypergraph in a weighted cycle
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• High Performance Computing - HiPC 2003
• A polynomial-time approximation scheme for embedding hypergraph in a cycle

Cites work

• A linear time algorithm for optimal routing around a rectangle
• Algorithms for routing around a rectangle
• scientific article; zbMATH DE number 1522943 (Why is no real title available?)
• Improved approximation algorithms for embedding hyperedges in a cycle
• Provably good moat routing
• Randomized metarounding (extended abstract)

Cited in

(6)

• A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring
• On packing and coloring hyperedges in a cycle
• Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• High Performance Computing - HiPC 2003
• A 2-approximation algorithm for an embedded hypergraph in a weighted cycle

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

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