@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.}
}
@article {17603,
	title = {Improved Algorithms via Approximations of Probability Distributions},
	journal = {Journal of Computer and System Sciences},
	volume = {61},
	year = {2000},
	month = {2000/08//},
	pages = {81 - 107},
	abstract = {We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veli{\v c}kovi{\'c}.},
	keywords = {derandomization, discrepancy, explicit constructions, graph coloring, Parallel algorithms, small sample spaces},
	isbn = {0022-0000},
	doi = {10.1006/jcss.1999.1695},
	url = {http://www.sciencedirect.com/science/article/pii/S0022000099916951},
	author = {Chari,Suresh and Rohatgi,Pankaj and Srinivasan, Aravind}
}
