Ross McConnell: Research

My research is on graph theory and algorithms. My recent work has been on circular-arc graphs, probe interval graphs, text-searching algorithms, modular decomposition of graphs and related structures, and transitive orientation of graphs. For an introduction to some of these problems, see the following texts:

The following give updated surveys of applications of these problems, and talk about some of the papers that I have listed below:

The following gives a lengthy treatment of results from the 1987 and two 1984 papers on text algorithms that I have listed below:

With Andrzej Ehrenfeucht at the University of Colorado at Boulder, I have recently co-developed a new data structure, the position heap for searching for substrings of a text in sublinear time. My Ph.D. student, Sung-Whan Woo has developed algorithms for updating this data structure when the text is edited. Click here to see a neat animation of Woo's algorithms.

Next year I'm a member of the Program Committee of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science.

I was an Invited Speaker at the European Graduate Program on Combinatorics, Geometry, and Computation lecture series on December 8, 2003 in Berlin.

I was one of five invited keynote speakers at the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, March 4-8, 2002, Boca Raton, Florida. The conference hosted about two hundred talks.

I was an Invited Plenary Speaker at the Second Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms, June 17-20, 2002, Haifa, Israel.

Journal Papers

  1. D. Kratsch, R.M. McConnell, K. Mehlhorn, J.P. Spinrad, Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs, SIAM Journal on Computing, 36(2) 2006, 326-353.

  2. G. Duran, A. Gravano, R. M. McConnell, J.P. Spinrad, A. Tucker, Polynomial time recognition of unit circular-arc graphs Journal of Algorithms,, 58 (2006) 67-78.

  3. R.M. McConnell and F. de Montgolfier, Linear-time modular decomposition of directed graphs, Discrete Applied Mathematics, 145(2) 2005, 189-209.

  4. R.M. McConnell, Linear-time recognition of circular-arc graphs, Algorithmica , 37 (2003), 93-147.

  5. W.L. Hsu and R.M. McConnell, PC trees and circular-ones arrangements (pdf), Theoretical Computer Science, 296(1) (2003), 59-74.

  6. E. Dahlhaus, J. Gustedt, R.M. McConnell, Partially complemented representations of digraphs (pdf) , Discrete Mathematics and Theoretical Computer Science, 5 (2002), 147-168. postscript version.

  7. E. Dahlhaus, J. Gustedt, R.M. McConnell, Efficient and practical algorithms for sequential modular decomposition,, Journal of Algorithms, 41 (2001), 360-387.

  8. P. Bonizzoni and R.M. McConnell, Nesting of prime structures in k-ary relations, Theoretical Computer Science, 259 (2001), 341-357.

  9. R.M. McConnell, J.P. Spinrad, Ordered vertex partitioning, Discrete Mathematics and Theoretical Computer Science, 4 (2000), 45-60. pdf version.

  10. M. Habib, R.M. McConnell, C. Paul, L. Viennot, Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing, Theoretical Computer Science, 234 (2000), 59-84.

  11. R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Mathematics, 201 (1999), 189-241. Selected by the editorial board to appear in the special issue Discrete Mathematics, Editors' Choice, Edition 1999. See also the Preface to the Editor's Choice Edition.

  12. R.M. McConnell, An O(n^2) incremental algorithm for modular decomposition of graphs and two-structures, Algorithmica, 14 (1995), 209-227.

  13. A. Ehrenfeucht, H.N. Gabow, R.M. McConnell and S.J. Sullivan, An O(n^2) Divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs, Journal of Algorithms, 16 (1994), 283-294.

  14. A. Ehrenfeucht and R.M. McConnell, A k-structure generalization of the theory of two-structures, Theoretical Computer Science, 132 (1994), 209-227.

  15. R. McConnell, R. Kwok, J.C. Curlander, W. Kober, and S. S. Pang. Psi-s correlation and dynamic time warping: two methods for tracking ice floes in SAR images, IEEE Transactions on Geoscience and Remote Sensing, 29 (1991), 1004-1012.

  16. R. Kwok, J.C. Curlander, R. McConnell, and S. S. Pang. An ice-motion tracking system at the Alaska SAR facility, IEEE Journal of Oceanic Engineering, 15 (1990), 44-54.

  17. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. McConnell, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM, 34 (1987), 578-595.

  18. B. Clift, D. Haussler, R. McConnell, T.D. Schneider, and G.D. Stormo. Sequence Landscapes, Nucleic Acids Research, 14 (1986), 141-158.

  19. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R. McConnell, Linear size finite automata for the set of all subwords of a word: an outline of results, Bulletin of the European Association of Theoretical Computer Science, 21 (1983), 12-20.

Conference Papers

  1. M.C. Lin, R.M. McConnell, F. Soulignac, J. Szwarcfiter, On cliques of Helly circular-arc graphs, Latin American Algorithms, Graphs, and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics 30 (2008) 117-122.

  2. A. Curtis, D. Massey, R.M. McConnell, Efficient algorithms for optimizing policy-constrained routing, International Workshop on Quality of Service (IWQoS), 2007.

  3. K. Nibbelink, S. Rajopadhye, R. M. McConnell, Knapsack on hardware: a complete solution, 18th IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP 2007), Montreal, July 8-11,2007.

  4. A. Curtis, C. Izurieta, B. Joeris, S. Lundberg, R.M. McConnell, An implicit representation of chordal comparability graphs in linear time, 32nd International Conference on Graph-Theoretic Concepts in Computer Science, Bergen, Norway, June 2006, LNCS 4271, pp. 168-178.

  5. A. Berry, R.M. McConnell, A. Sigayret, J.P. Spinrad, Very fast instances for concept generation, International Conference on Formal Concept Analysis (ICFCA'06), B. Ganter and L. Kwuida Eds., LNAI 3874 (2006) 119-129.

  6. R.M. McConnell and F. de Montgolfier, Algebraic operations on PQ trees and modular decomposition trees, Thirty-First International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 3787 (2005), 421-432.

  7. I. Ray, E. Kim, D. Massey, R. McConnell, Reliably, Securely and Efficiently Distributing Electronic Content Using Multicasting, EC-Web 2005.

  8. A. Berry, M. Huchard, R. M. McConnell, A. Sigayret, J.P. Spinrad, Efficiently computing a linear extension of the sub-hierarchy of a concept lattice, Proceedings of the Third International Conference on Formal Concept Analysis (2005), 208-217.

  9. R.M. McConnell, A certifying algorithm for the consecutive-ones property, ACM-SIAM SODA, 15 (2004), 761-770.

  10. I. Ray, M. Lunacek, R.M. McConnell, V. Kumar, Reducing damage assessment latency in survivable databases, Proceedings of the 21st Annual British National Conference on Databases, Lecture Notes in Computer Science, 3112 (2004).

  11. D. Kratsch, R.M. McConnell, K. Mehlhorn, J.P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs (pdf), ACM-SIAM SODA, 14 (2003), 866-875.

  12. R.M. McConnell and J.P. Spinrad, Construction of probe interval models (pdf), Proceedings of the ACM-SIAM SODA 13 (2002), 866-875.

  13. R.M. McConnell, Linear time recognition of circular-arc graphs, IEEE FOCS 42 (2001), 386-394.

  14. R.M. McConnell and J.P. Spinrad, Linear-time transitive orientation, ACM-SIAM SODA 8 (1997), 19-25.

  15. E. Dahlhaus, J. Gustedt, and R. McConnell, Efficient and practical modular decomposition, ACM-SIAM SODA 8 (1997), 26-35.

  16. R.M. McConnell and J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, ACM-SIAM SODA 5 (1994), 536-545.

  17. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R. McConnell, Building a complete inverted file for a set of text files in linear time, ACM STOC, 16 (1984), Washington, D.C. 349-358.

  18. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R. McConnell, Building the minimum DFA for the set of all subwords of a word on-line in linear time. Eleventh International Colloquium on Automata, Languages and Programming (ICALP84) (1984), volume 172 of Lecture Notes in Computer Science, pp. 109-118, Springer-Verlag.

Invited Papers and Book Chapters