Dr Steven Noble

Contact

Mathematical Sciences John Crank 106 Brunel University Uxbridge UB8 3PH United Kingdom

Tel: +44 (0)1895 265619 Fax: +44 (0)1895 269732 Email: steven.noble@brunel.ac.uk Web: Personal Website

Research Interests

Graph theory, complexity of algorithms and combinatorial optimisation, particularly enumeration problems and graph polynomials such as the Tutte polynomial, the frequency assignment problem, graph colouring and labelling problems.

University Research Centre Membership

Research Group Membership

Publications

Journal Papers

(2012) Noble, SD., Merino, C., Ramirez-Ibanez, M. and Villarroel-Flores, R., On the structure of the h-vector of a paving matroid., European Journal of Combinatorics 33 1787- 1799

(2012) Lin, Y., Noble, SD., Jin, X. and Cheng, W., On plane graphs with link component number equal to the nullity, Discrete Applied Mathematics 160 (9) : 1369- 1375

(2012) Eggemann, N. and Noble, SD., The complexity of two graph orientation problems, Discrete Applied Mathematics 160 (4-5) : 513- 517 Download publication

(2011) Noble, SD., Hansen, P. and Mladenović, N., Maximizing edge-ratio is NP-complete, Discrete Applied Mathematics 159 (18) : 2276- 2280 Download publication

(2011) Chávez-Lomelí, LE., Merino, C., Noble, SD. and Ramírez-Ibáñez, M., Some inequalities for the Tutte polynomial, European Journal of Combinatorics 32 422- 433 Download publication

(2011) Eggemann, N. and Noble, SD., The clustering coefficient of a scale-free random graph, Discrete Applied Mathematics 159 (10) : 953- 965 Download publication

(2011) Goodall, AJ., de Mier, A., Noble, SD. and Noy, M., The Tutte polynomial characterizes simple outerplanar graphs, Combinatorics, Probability and Computing 20 (4) : 609- 616 Download publication

(2011) Goodall, AJ., de Mier, A., Noble, SD. and Noy, M., The Tutte polynomial characterizes simple outerplanar graphs, Electronic Notes in Discrete Mathematics 38 639- 644

(2010) Eggemann, N., Havet, F. and Noble, SD., k-L(2,1)-labelling for planar graphs is NP-complete for k >= 4, Discrete Applied Mathematics 158 (16) : 1777- 1788 Download publication

(2009) Noble, SD., Evaluating a weighted graph polynomial for graphs of bounded tree-width, The Electronic Journal of Combinatorics 16 (1) : R64 Download publication

(2009) Eggemann, N. and Noble, SD., Minimizing the oriented diameter of a planar graph, Electronic Notes in Discrete Mathematics 34 267- 271 Download publication

(2009) Merino, C. and Noble, SD., The equivalence of two graph polynomials and a symmetric function, Combinatorics, Probability and Computing 18 (4) : 601- 615 Download publication

(2006) Noble, SD., Evaluating the rank generating function of a graphic 2-polymatroid, Combinatorics, Probability and Computing 15 (3) : 449- 461 Download publication

(2004) Leese, RA. and Noble, SD., Cyclic labellings with constraints at two distances, Electronic Journal of Combinatorics 11 (1) : 1- 16 Download publication

(2004) Koller, AE. and Noble, SD., Domination analysis of greedy heuristics for the frequency assignment problem, Discrete Mathematics 275 (1-3) : 331- 338 Download publication

(2004) Krasikov, I. and Noble, SD., Finding next-to-shortest paths in a graph, Information Processing Letters 92 (3) : 117- 119 Download publication

(2003) Calkin, N., Merino, C., Noble, S. and Noy, M., Improved bounds for the number of forests and acyclic orientations in the square lattice, Electronic Journal of Combinatorics 10 (1) : 1- 18 Download publication

(2001) Luczak, M.J.. and Noble, SD., Optimal arrangement of data in a tree directory, Discrete Applied Mathematics 113 (2-3) : 243- 253 Download publication

(2000) Noble, SD. and Welsh, DJA., Knot graphs, Journal of Graph Theory 34 (1) : 100- 111 Download publication

(1999) Noble, SD. and Welsh, DJA., A weighted graph polynomial from chromatic invariants of knots, Annales de l'Institut Fourier 49 (3) : 1057- 1087

(1998) Noble, SD., Evaluating the Tutte polynomial for graphs of bounded tree-width, Combinatorics, Probability and Computing 7 (3) : 307- 321 Download publication

(1996) Noble, SD., Recognising a partitionable simplicial complex is in NP, Discrete Mathematics 152 (1-3) : 303- 305 Download publication

Book Chapters

(2007) Noble, SD., Complexity of graph polynomials. In: Grimmett, G. and McDiarmid, C. eds. Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh. Oxford University Press 191- 212