Current Proceedings on Technology

Current Proceedings on Technology

2-Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle Rings

Yazarlar: Xiaoshan Liu, Qi Wang

Cilt 3 , Sayı - , 2013 , Sayfalar -

Konular:-

Anahtar Kelimeler:Hypergraph,Embedding,Polynomial-time approximation scheme (PTAS)

Özet: A cycle rings is an undirected graph obtained from a cycle by replacing each edge of the cycle with a ring so that two rings corresponding to the two end-nodes of any edge have precisely one node in common. Given a weighted hypergraph on a cycle rings , Minimum-Congestion Weighted Hypergraph Embedding in a cycle rings (WHECR) is to embed each weighted hyperedges as a path in the cycle rings such that maximal congestion-the sum of weight of embedding paths that use any edge in the cycle rings -is minimized. We prove that the WHECR problem is NP-complete. 2-approximation algorithms are presented for the WHECR problem.

ATIFLAR
Atıf Yapan Eserler
Henüz Atıf Yapılmamıştır
KAYNAK GÖSTER
BibTex
KOPYALA
@article{2013, title={2-Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle Rings}, volume={3}, number={0}, publisher={Current Proceedings on Technology }, author={Xiaoshan Liu, Qi Wang}, year={2013} }
APA
KOPYALA
Xiaoshan Liu, Qi Wang. (2013). 2-Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle Rings (Vol. 3). Vol. 3. Current Proceedings on Technology .
MLA
KOPYALA
Xiaoshan Liu, Qi Wang. 2-Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle Rings. no. 0, Current Proceedings on Technology , 2013.
Atıf Görüntüle
PDF Görüntüle
Kaynak Görüntüle
Paylaş
Dergi Bilgileri