The Library
Polynomial-time construction of linear network coding
Tools
Tools
Tools
Iwama, Kazuo, Nishimura, Harumichi, Paterson, Michael S., Raymond, Rudy and Yamashita, Shigeru (2008) Polynomial-time construction of linear network coding. In: ICALP 2008: 35th International Colloquium on Automata, Languages and Programming , Reykjavik, Iceland, 6 - 13 Jul 2008 . Published in: Lecture Notes in Computer Science, Vol.5125 pp. 271-282. doi:10.1007/978-3-540-70575-8_23 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-540-70575-8_23
Abstract
Constructing k independent sessions between k source-sink pairs with the help of a linear operation at each vertex is one of the most standard problems in network coding. For an unbounded k, this is known to be NP-hard. Very recently, a polynomial-time algorithm was given for k = 2 [Wang and Shroff, ISIT 2007], but was open for a general (constant) k. This paper gives a polynomial-time algorithm for this problem under the assumption that the size of the finite field for the linear operations is bounded by a fixed constant.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Automata, Languages and Programming | ||||
| Official Date: | 2008 | ||||
| Dates: |
|
||||
| Volume: | Vol.5125 | ||||
| Page Range: | pp. 271-282 | ||||
| DOI: | 10.1007/978-3-540-70575-8_23 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Description: | ICALP '08 Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I |
||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | ICALP 2008: 35th International Colloquium on Automata, Languages and Programming | ||||
| Type of Event: | Other | ||||
| Location of Event: | Reykjavik, Iceland | ||||
| Date(s) of Event: | 6 - 13 Jul 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
