Ross McConnell: Research

I was a volume editor on Graph Theory, Computational Intelligence and Thought, 2009.

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:

• M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, Boston, 1980.

• F.S. Roberts, Graph Theory and Its Applications to Problems of Society, Society for Industrial and Applied Mathematics, Philadelphia, 1978.

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

• Andreas Brandstaedt, Van Bang Le, Jeremy P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, 1999.

• Jeremy P. Spinrad, Efficient Graph Representations, American Mathematical Society, Providence, Rhode Island, 2003.

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

• Crochemore, M., Rytter, W., Text Algorithms, Oxford University Press, 1994.

  ---

  Publications

  1. Vinicius Fernandes dos Santos, Michel Habib, Denis Julien, Ross M. McConnell, Jayme Szwarcfiter, Clique Graphs of Chordal Comparability Graphs, Latin American Workshop on Cliques in Graphs, accepted.

  2. Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy Spinrad, Jayme Luiz Szwarcfiter, Linear-Time Recognition of Helly Circular-Arc Models and Graphs. Algorithmica 59(2): 215-239 (2011).

  3. Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, Pascal Schweitzer, Certifying algorithms, Computer Science Review 5(2): 119-161 (2011).

  4. Andrzej Ehrenfeucht, Ross M. McConnell, Nissa Osheim, Sung-Whan Woo, Position heaps: A simple and dynamic text indexing data structure, J. Discrete Algorithms 9(1): 100-121 (2011).
     • Click here For C++ code demonstrating algorithms from the paper

  5. Manachai Toahchoodee, Indrakshi Ray, Ross M. McConnell, Using Graph Theory to Represent a Spatio-Temporal Role-Based Access Control Model. IJNGC 1(2): (2010).

  6. A. Curtis, B.L. Joeris, C. Izurieta, S. Lundberg, R.M. McConnell, An implicit representation of chordal comparability graphs in linear time, Discrete Applied Mathematics 158 (2010) 869-875.

  7. B.L. Joeris, S. Lundberg, R.M. McConnell, O(m log n) split decomposition of strongly-connected graphs, Discrete Applied Mathematics, 158(7) (2010), 779-799.

  8. R.M. McConnell and Y. Nussbaum, Linear-time recognition of probe interval graphs, Proceedings of the European Symposium on Algorithms (ESA) 2009, 349-360.

  9. A. Ehrenfeucht, R.M. McConnell, S.-W. Woo, Contracted suffix trees: a simple and dynamic text indexing data structure, Combinatorial Pattern Matching (2009) 41-53.

  10. B.L. Joeris, S. Lundberg, R.M. McConnell, O(m log n) split decomposition of strongly-connected graphs, Proceedings Graph Theory, Computational Intelligence and Thought, Haifa, September 2008, Lecture Notes in Computer Science 5420, (2009), pp 158-171.

  11. 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.

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

  13. 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.

  14. 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.

  15. 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.

  16. 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.

  17. 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.

  18. 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.

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

  20. 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.

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

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

  23. 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).

  24. 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.

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

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

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

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

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

  30. 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.
  31. R.M. McConnell, Linear time recognition of circular-arc graphs, IEEE FOCS 42 (2001), 386-394.

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

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

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

  35. 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.

  36. 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.

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

  38. 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.

  39. 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.

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

  41. 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.

  42. 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.

  43. 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.

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

  45. 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.

  46. 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.

  47. 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.

  Invited Papers and Book Chapters

  • A. Ehrenfeucht, and R.M. McConnell, String Searching, Handbook of Data Structures and Applications, (Dinesh Mehta and Sartaj Sahni, ed.) CRC Press, 2005.

  • W.L. Hsu and R.M. McConnell, PQ Trees, PC Trees, and Planar Graphs, Handbook of Data Structures and Applications, (Dinesh Mehta and Sartaj Sahni, ed.) CRC Press, 2005.

  • R.M. McConnell, Decompositions and forcing relationsin graphs and other combinatorial structures, for Graph Theory, Combinatorics, and Algorithms: Interdisciplinary Applications, (Martin C. Golumbic and Irith Ben-Arroyo Hartman ed.), 2005.

  • Dahlhaus, E., J. Gustedt, R.M. McConnell, Graph Algorithms and the Outward Equivalence Relation, Journ'ees de l'Informatique Messine, (2000) 55-62.

  • R.M. McConnell, Complement-equivalence classes on graphs, in Structures in Logic and Computer Science, J. Mycielski, G. Rozenberg, A. Salomaa (editors), Springer (1997).