@conference {17559,
	title = {Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints},
	booktitle = {IEEE INFOCOM 2008. The 27th Conference on Computer Communications},
	year = {2008},
	month = {2008/04/13/18},
	pages = {1166 - 1174},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.},
	keywords = {Algorithm design and analysis, approximation algorithm, Approximation algorithms, approximation theory, Computer networks, Computer science, graph theory, graph-based model, Interference constraints, polynomial time algorithm, Propagation losses, Protocols, radio networks, radiofrequency interference, signal to interference plus noise ratio, Signal to noise ratio, Throughput, wireless interference, wireless network, Wireless networks},
	isbn = {978-1-4244-2025-4},
	doi = {10.1109/INFOCOM.2008.172},
	author = {Chafekar,D. and Kumart,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind}
}
@conference {14563,
	title = {Algorithmic graph minor theory: Decomposition, approximation, and coloring},
	booktitle = {Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on},
	year = {2005},
	month = {2005///},
	pages = {637 - 646},
	abstract = {At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.},
	keywords = {algorithmic graph minor theory, approximation algorithm, combinatorial polylogarithmic approximation, computational complexity, constant-factor approximation, graph algorithm, graph coloring, graph colouring, half-integral multicommodity flow, largest grid minor, maximization problem, minimization problem, polynomial-time algorithm, subexponential fixed-parameter algorithm, topological graph theory, treewidth},
	doi = {10.1109/SFCS.2005.14},
	author = {Demaine,E. D and Hajiaghayi, Mohammad T. and Kawarabayashi,K.}
}
