A polynomial time approximation scheme for embedding hypergraph in a weighted cycle

DOI10.1016/j.tcs.2011.08.014zbMath1228.68034OpenAlexW1972142999MaRDI QIDQ650915

Chaoxia Yang, Guo Jun Li

Publication date: 7 December 2011

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

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

zbMATH Keywords

NP-hardweighted cyclepolynomial time approximation schemehypergraph embeddingminimum congestion

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The weighted link ring loading problem
• Edge-disjoint paths in planar graphs
• Algorithms for routing around a rectangle
• On the closest string and substring problems
• Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle
• A polynomial-time approximation scheme for embedding hypergraph in a cycle

This page was built for publication: A polynomial time approximation scheme for embedding hypergraph in a weighted cycle