Improved approximation algorithms for embedding hyperedges in a cycle

DOI10.1016/S0020-0190(98)00117-3MaRDI QIDQ293373zbMATHFDO

Authors 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

approximation algorithmsparallel computationCADlinear time algorithmsminimize congestion

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

Cited in

(8)

• On packing and coloring hyperedges in a cycle
• A polynomial time approximation scheme for embedding a directed hypergraph on a ring
• High Performance Computing - HiPC 2003
• A polynomial-time approximation scheme for embedding hypergraph in a cycle
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring
• Automata, Languages and Programming

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

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