Iwama, Kazuo, Nishimura, Harumichi, Paterson, Mike, 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.

Full text not available from this repository.

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 > Computer Science
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISSN:	0302-9743
Book Title:	Automata, Languages and Programming
Date:	2008
Volume:	Vol.5125
Page Range:	pp. 271-282
Identification Number:	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
URI:	http://wrap.warwick.ac.uk/id/eprint/42380

Request changes to a record

Actions (login required)

View Item