Ross McConnell: Research

Publications

1. Pavol Hell, Jing Huang, Jephian C.-H. Lin, Ross M. McConnell, Bipartite Analogues of Comparability and Cocomparability Graphs SIAM J. Discrete Math., to appear.

2. Pavol Hell, Jing Huang, Ross M. McConnell, Arash Rafiey, Min-Orderable Digraphs, SIAM J. Discrete Math. 34-3 (2020), pp. 1710-1724.

3. Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, Zhisheng Xu, Double threshold digraphs, 43rd International Symposium on Mathematical Foundations of Computer Science, 68:1-13 (2018).

4. Pavol Hell, Jing Huang, Ross M. McConnell, Arash Rafiey, Interval-like graphs and digraphs, 43rd International Symposium on Mathematical Foundations of Computer Science, 69:1-13 (2018).

5. M. Chaturvedi, R. M. McConnell, A note on finding minimum mean cycle, Information Processing Letters, 127: 21-22 (2017).

6. Benson Joeris, Nathan Lindzey, Ross M. McConnell, Nissa Osheim, Simple DFS on the complement of a graph and on partially complemented digraphs, Information Processing Letters, 117: 35-39 (2017).

7. P. Golovach, P. Heggernes, N. Lindzey, R.M. McConnell, V. dos Santos, J.P. Spinrad, On recognition of threshold tolerance graphs and their complements" Discrete Applied Mathematics, 216: 171-180 (2017).

8. Nathan Lindzey, Ross M. McConnell, Linear-time algorithms for finding Tucker matrices and Lekkerkerker-Boland subgraphs SIAM Journal on Discrete Math, 30(1): 43-69 (2016).

9. Ross M. McConnell, Yahav Nussbaum, Linear-Time Recognition of Probe Interval Graphs, SIAM Journal on Discrete Mathematics, 29(4) 2006-2046 (2015).

10. P. Golovach, P. Heggernes, N. Lindzey, R.M. McConnell, V. dos Santos, J.P. Spinrad, Recognizing Threshold Tolerance Graphs in O(n^2) time, Proceedings of the 40th International Workshop on Graph Theoretic Concepts in Computer Science, 214-224 (2014).

11. Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum, Francisco J. Soulignac, Jeremy Spinrad, Jayme Luiz Szwarcfiter, Isomorphism of graph classes related to the circular-ones property, Discrete Mathematics & Theoretical Computer Science 15(1): 157-182 (2013).

12. Nathan Lindzey, Ross M. McConnell, On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs, Proceedings of the Thirty-ninth International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013): 345-357, 2013.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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