A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)319-328
Journal / PublicationJournal of Combinatorial Optimization
Volume24
Issue number3
Publication statusPublished - Oct 2012
Externally publishedYes

Abstract

Given a directed hypergraph H = (V ,E H ), we consider the problem of embedding all directed hyperedges on a weighted ring. The objective is to minimize the maximum congestion which is equal to the maximum product of the weight of a link and the number of times that the link is passed by the embedding. In this paper, we design a polynomial time approximation scheme for this problem. © Springer Science+Business Media, LLC 2011.

Research Area(s)

  • Directed hypergraph, Embedding, PTAS