Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home People Profile

Bruce Reed


photo

Email: breed AT cs DOT mcgill DOT ca
Home Page: http://cgm.cs.mcgill.ca/~breed/
Office: MC301
Phone: +1-514-398-5913
Fax: +1-514-398-3883
Address:

Research Description

Professor Reed's main research area is algorithmic graph theory. Graphs are used to model both physical and abstract networks, including the world wide web, the wiring on a computer chip, and telecommunications networks. Professor Reed is interested in applying structural decomposition techniques and probabilistic methods to find efficient algorithms for solving various theoretical optimization problems on graphs.

Research Interests

Research Labs

Teaching

Selected Publications (click link in front of each publication to see bibtex in ASCII format)

[1] Cerioli, M., Faria, L., Ferreira, T., Martinhon, C., Protti, F., and Reed, B. Partition into cliques for cubic graphs: Planar case, complexity and approximation. Discrete Applied Mathematics, 2008, v. 156, pp. 2270-2278.
[2] Addario-Berry, L., Dalal, K., and B.Reed. Degree-constrained subgraphs. Discrete Applied Mathematics, 2008, v. 156, pp. 1168-1174.
[3] Addario-Berry, L., Chudnovsky, C., Havet, F., Reed, B., and Seymour, P. Bisimplicial ver- tices in even hole free graphs. Journal of Combinatorial Theory, 2008, v. 98 of B, B, pp. 1119-1164.
[4] Fiorini, S., Hardy, N., Reed, B., and Vetta, A. Planar graph bipartization in linear time. Discrete Applied Mathematics, 2008, v. 156, pp. 1175-1180.
[5] Kawarabayashi, K., Lee, O., Reed, B., and Wollan, P. A weaker version of lovasz’ path re- movable conjecture. Journal of Combinatorial Theory, 2008, v. 98 of B, B, pp. 972-979.
[6] Kawarabayashi, K., and Reed, B. Fractional coloring and the odd hadwiger’s conjecture. Euro. J. Comb., 2008, v. 29, n. 2, pp. 411-417.
[7] Linhares-Sales, C., Maffray, F., and Reed, B. On planar quasi-parity graphs. SIAM J. Discrete Mathematics, 2008, v. 22, pp. 329-347.
[8] Meagher, C., and Reed, B. Fractionally total colouring gn,p. Discrete Applied Mathematics, 2008, v. 156, pp. 1112-1124.
[9] Reed, B. Skew partitions in perfect graphs. Discrete Applied Mathematics, 2008, v. 156, pp. 1150-1156.
[10] Addario-Berry, L., and Reed, B. Ballot Theorems, Old and New. Bolyai Society Mathematical Studies Series 17, 2008.
[11] Kawarabayashi, K., and Reed, B. A nearly linear time algorithm for the half integral disjoint paths packing. Proceedings of SODA, 2008.
[12] Kawarabayashi, K., Mohar, B., and Reed, B. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. Proceedings of FOCS, 2008. In Press.
[13] Fountoulakis, N., and Reed, B. Faster mixing and small bottlenecks. Probability Theory and Related Fields, 2007, v. 137, pp. 475-486. (received acceptance in 2006).
[14] Bondy, A., Avis, D., Cook, W., and Reed, B. Vasek chvatal: A short introduction. Graphs and Combinatorics, 2007, v. 23, pp. 41-66.
[15] Addario-Berry, L., Delal, K., McDiarmid, C., Reed, B., and Thomason, A. Vertex colouring edge weightings. Combinatorica, 2007, v. 27, pp. 1-12.
[16] Birmele, E., Bondy, J. A., and Reed, B. Brambles, prisms and grids, graph theory in paris. In Proceedings of a Conference in Memory of Claude Berge, Birkhauser, Basel. 2007, pp. 37-44.
[17] Birmele, E., Bondy, J. A., and Reed, B. The erdos-posa proprty for long circuits. Combinatorica, 2007, v. 27, pp. 135-145.
[18] Kawarabayashi, K., and Reed, B. Computing crossing numbers in linear time. In Proceedings of STOC 2007, 2007, pp. 382-390.
[19] Mcdiarmid, C., and Reed, B. Concentration for self-bounding functions and an inequality of talagrand. Random Structures and Algorithms, 2006, v. 29, pp. 549-557.
[20] Bang-Jensen, J., Reed, B., Schacht, M., Šámal, R., Toft, B., and Wagner, U. On six problems posed by jarik nešetřil. Topics in Discrete Mathematics, 2006, v. 26 of Algorithms Combin., Algorithms Combin., pp. 613-627.
[21] Kawarabayashi, K., and Reed, B. Highly linked parity graphs. Combinatorica, 2006. In Press.
[22] Reed, B. Skew partitions in perfect graphs. Discrete Applied Mathematics, 2006. In Press.
[23] Birmele, E., Bondy, J. A., and Reed, B. Brambles, prisms and grids. In Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris, Basel. Birkhauser, 2006, pp. 37-44.
[24] Addario-Berry, L., Broutin, N., and Reed, B. The diameter of the minimum spanning tree of a complete graph. In Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006.

Last Update:   2013/08/05 09:01:52.655 GMT-4