Improved approximation algorithms for embedding hyperedges in a cycle

DOI10.1016/S0020-0190(98)00117-3zbMath1339.68317MaRDI QIDQ293373

Teofilo F. Gonzalez

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001173?np=y

zbMATH Keywords

parallel computationapproximation algorithmsCADlinear time algorithmsminimize congestion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (4)

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

Cites Work

• Algorithms for routing around a rectangle
• A $1.6$ Approximation Algorithm for Routing Multiterminal Nets
• A linear time algorithm for optimal routing around a rectangle
• Provably good moat routing

This page was built for publication: Improved approximation algorithms for embedding hyperedges in a cycle