An approximation algorithm for embedding a directed hypergraph on a ring

Kang Li; Lusheng Wang

doi:10.1007/11496199_42

An approximation algorithm for embedding a directed hypergraph on a ring

Kang Li
, Lusheng Wang

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. © Springer-Verlag Berlin Heidelberg 2005.

Original language	English
Title of host publication	Algorithmic Applications in Management
Subtitle of host publication	First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings
Publisher	Springer
Pages	392-399
ISBN (Electronic)	978-3-540-32440-9
ISBN (Print)	978-3-540-26224-4
DOIs	https://doi.org/10.1007/11496199_42
Publication status	Published - 2005
Event	1st Annual International Conference on Algorithmic Applications in Management (AAIM'05) - Xian, China Duration: 22 Jun 2005 → 25 Jun 2005

Publication series

Name	Lecture Notes in Computer Science
Volume	3521
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st Annual International Conference on Algorithmic Applications in Management (AAIM'05)
Place	China
City	Xian
Period	22/06/05 → 25/06/05

Access Output

10.1007/11496199_42

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{fd1e832611234640a7992cfd1aed838f,

title = "An approximation algorithm for embedding a directed hypergraph on a ring",

abstract = "We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. {\textcopyright} Springer-Verlag Berlin Heidelberg 2005.",

author = "Kang Li and Lusheng Wang",

year = "2005",

doi = "10.1007/11496199\_42",

language = "English",

isbn = "978-3-540-26224-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "392--399",

booktitle = "Algorithmic Applications in Management",

note = "1st Annual International Conference on Algorithmic Applications in Management (AAIM'05) ; Conference date: 22-06-2005 Through 25-06-2005",

}

Li, K & Wang, L 2005, An approximation algorithm for embedding a directed hypergraph on a ring. in Algorithmic Applications in Management: First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3521, Springer , pp. 392-399, 1st Annual International Conference on Algorithmic Applications in Management (AAIM'05), Xian, China, 22/06/05. https://doi.org/10.1007/11496199_42

An approximation algorithm for embedding a directed hypergraph on a ring. / Li, Kang; Wang, Lusheng.
Algorithmic Applications in Management: First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings. Springer , 2005. p. 392-399 (Lecture Notes in Computer Science; Vol. 3521).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An approximation algorithm for embedding a directed hypergraph on a ring

AU - Li, Kang

AU - Wang, Lusheng

PY - 2005

Y1 - 2005

N2 - We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. © Springer-Verlag Berlin Heidelberg 2005.

AB - We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. © Springer-Verlag Berlin Heidelberg 2005.

UR - https://www.scopus.com/pages/publications/25144495117

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-25144495117&origin=recordpage

U2 - 10.1007/11496199_42

DO - 10.1007/11496199_42

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-540-26224-4

T3 - Lecture Notes in Computer Science

SP - 392

EP - 399

BT - Algorithmic Applications in Management

PB - Springer

T2 - 1st Annual International Conference on Algorithmic Applications in Management (AAIM'05)

Y2 - 22 June 2005 through 25 June 2005

ER -

An approximation algorithm for embedding a directed hypergraph on a ring

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this