Campus Units

Electrical and Computer Engineering

Document Type

Conference Proceeding

Conference

2010 48th Annual Allerton Conference on Communication, Control, and Computing

Publication Version

Accepted Manuscript

Link to Published Version

https://doi.org/10.1109/ALLERTON.2010.5707000

Publication Date

2011

Journal or Book Title

2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

DOI

10.1109/ALLERTON.2010.5707000

Conference Title

2010 48th Annual Allerton Conference on Communication, Control, and Computing

Conference Date

September 29-October 1, 2010

City

Allerton, IL

Abstract

The work of Avestimehr et al. '07 has recently proposed a deterministic model for wireless networks and characterized the unicast capacity C of such networks as the minimum rank of the adjacency matrices describing all possible source-destination cuts. Amaudruz & Fragouli first proposed a polynomial-time algorithm for finding the unicast capacity of a linear deterministic wireless network in their 2009 paper. In this work, we improve upon Amaudruz & Fragouli's work and further reduce the computational complexity of the algorithm by fully exploring the useful combinatorial features intrinsic in the problem. Our improvement applies generally with any size of finite fields associated with the channel model. Comparing with other algorithms on solving the same problem, our improved algorithm is very competitive in terms of complexity.

Comments

This is a manuscript of a proceeding from the 48th Annual Allerton Conference on Communication, Control, and Computing (2010): 875, doi:10.1109/ALLERTON.2010.5707000. Posted with permission.

Rights

Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Copyright Owner

IEEE

Language

en

File Format

application/pdf

Published Version

Share

 
COinS