Derek G. Corneil

114 papers A* 5A 2B 12Journal 91Unranked 2
YearRankTypeTitle / Venue / Authors
2025 J jnl
Lower bounds on collective additive spanners.
CoRR
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Yang Xiang
2024 J jnl
Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications.
Order
Jérémie Dusart, Michel Habib, Derek G. Corneil
2021 J jnl
Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.
SIAM J. Comput.
Jérémie Dusart, Derek G. Corneil, Michel Habib
2020 J jnl
Foreword: Eighth Workshop on Graph Classes, Optimization, and Width Parameters, Toronto, Ontario, Canada.
Discret. Appl. Math.
Derek G. Corneil, Robert Ganian, Andrzej Proskurowski
2018 J jnl
Preface: Seventh Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015.
Discret. Appl. Math.
Derek G. Corneil, Sang-il Oum, Christophe Paul
2016 J jnl
A tie-break model for graph search.
Discret. Appl. Math.
Derek G. Corneil, Jérémie Dusart, Michel Habib, Antoine Mamcarz, Fabien de Montgolfier
2016 J jnl
Maximal cliques structure for cocomparability graphs and applications.
CoRR
Jérémie Dusart, Michel Habib, Derek G. Corneil
2016 J jnl
On the Power of Graph Searching for Cocomparability Graphs.
SIAM J. Discret. Math.
Derek G. Corneil, Jérémie Dusart, Michel Habib, Ekkehard Köhler
2016 — ch.
Unified View of Graph Searching and LDFS-Based Certifying Algorithms.
Encyclopedia of Algorithms
Derek G. Corneil, Michel Habib
2015 J jnl
A tie-break model for graph search.
CoRR
Derek G. Corneil, Jérémie Dusart, Michel Habib, Fabien de Montgolfier
2015 J jnl
Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number.
J. Graph Theory
Derek G. Corneil, Juraj Stacho
2014 J jnl
Practical and Efficient Circle Graph Recognition.
Algorithmica
Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil
2014 J jnl
Practical and Efficient Split Decomposition via Graph-Labelled Trees.
Algorithmica
Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil
2013 J jnl
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.
SIAM J. Comput.
Derek G. Corneil, Barnaby Dalton, Michel Habib
2012 J jnl
A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs.
SIAM J. Discret. Math.
George B. Mertzios, Derek G. Corneil
2012 J jnl
Collective additive tree spanners for circle graphs and polygonal graphs.
Discret. Appl. Math.
Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang
2012 J jnl
Polynomial-time recognition of clique-width ≤3 graphs.
Discret. Appl. Math.
Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, Udi Rotics
2011 J jnl
Circle Graph Recognition in Time O(n+m) α(n+m)
CoRR
Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil
2011 J jnl
Practical and Efficient Split Decomposition via Graph-Labelled Trees
CoRR
Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil
2011 J jnl
Vertex splitting and the recognition of trapezoid graphs.
Discret. Appl. Math.
George B. Mertzios, Derek G. Corneil
2010 J jnl
A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
CoRR
George B. Mertzios, Derek G. Corneil
2010 J jnl
On end-vertices of Lexicographic Breadth First Searches.
Discret. Appl. Math.
Derek G. Corneil, Ekkehard Köhler, Jean-Marc Lanlignel
2009 J jnl
The LBFS Structure and Recognition of Interval Graphs.
SIAM J. Discret. Math.
Derek G. Corneil, Stephan Olariu, Lorna Stewart
2008 J jnl
A Simple Linear Time LexBFS Cograph Recognition Algorithm.
SIAM J. Discret. Math.
Anna Bretscher, Derek G. Corneil, Michel Habib, Christophe Paul
2008 J jnl
A Unified View of Graph Searching.
SIAM J. Discret. Math.
Derek G. Corneil, Richard Krueger
2008 B conf
Additive Spanners for Circle Graphs and Polygonal Graphs.
WG
Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang
2008 — conf
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.
ICALP (1)
Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul
2007 A conf
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs.
STACS
Marc Tedder, Derek G. Corneil
2007 J jnl
Simple, linear-time modular decomposition
CoRR
Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul
2006 J jnl
Collective Tree Spanners and Routing in AT-free Related Graphs.
J. Graph Algorithms Appl.
Feodor F. Dragan, Chenyu Yan, Derek G. Corneil
2006 J jnl
Efficient estimation of graphlet frequency distributions in protein-protein interaction networks.
Bioinform.
Natasa Przulj, Derek G. Corneil, Igor Jurisica
2006 J jnl
Linear Orderings of Subfamilies of AT-Free Graphs.
SIAM J. Discret. Math.
Derek G. Corneil, Ekkehard Köhler, Stephan Olariu, Lorna Stewart
2005 J jnl
2-Tree probe interval graphs have a large obstruction set.
Discret. Appl. Math.
Natasa Przulj, Derek G. Corneil
2005 B conf
Collective Tree 1-Spanners for Interval Graphs.
WG
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan
2005 J jnl
On the Relationship Between Clique-Width and Treewidth.
SIAM J. Comput.
Derek G. Corneil, Udi Rotics
2005 J jnl
Simple vertex ordering characterizations for graph search: (expanded abstract).
Electron. Notes Discret. Math.
Derek G. Corneil, Richard Krueger
2004 — conf
04221 Abstracts Collection - Robust and Approximative Algorithms on Particular Graph Classes.
Robust and Approximative Algorithms an Particular Graph Classes
Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, Jeremy P. Spinrad
2004 J jnl
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs.
Discret. Appl. Math.
Derek G. Corneil
2004 B conf
Collective Tree Spanners and Routing in AT-free Related Graphs.
WG
Feodor F. Dragan, Chenyu Yan, Derek G. Corneil
2004 J jnl
Hereditary dominating pair graphs.
Discret. Appl. Math.
Natasa Przulj, Derek G. Corneil, Ekkehard Köhler
2004 B conf
Lexicographic Breadth First Search - A Survey.
WG
Derek G. Corneil
2004 J jnl
Modeling interactome: scale-free or geometric?.
Bioinform.
Natasa Przulj, Derek G. Corneil, Igor Jurisica
2004 J jnl
Recognizing Powers of Proper Interval, Split, and Chordal Graph.
SIAM J. Discret. Math.
Lap Chi Lau, Derek G. Corneil
2004 — ed.
Robust and Approximative Algorithms an Particular Graph Classes, 23.05. - 28.05.2004
Robust and Approximative Algorithms an Particular Graph Classes
Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, Jeremy P. Spinrad
2003 B conf
A Simple Linear Time LexBFS Cograph Recognition Algorithm.
WG
Anna Bretscher, Derek G. Corneil, Michel Habib, Christophe Paul
2003 J jnl
On the power of BFS to determine a graph's diameter.
Networks
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler
2002 J jnl
Automatic generation of synthetic sequential benchmark circuits.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
Michael D. Hutton, Jonathan Rose, Derek G. Corneil
2002 B conf
On the Power of BFS to Determine a Graphs Diameter.
LATIN
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler
2001 J jnl
Diameter determination on restricted graph families.
Discret. Appl. Math.
Derek G. Corneil, Feodor F. Dragan, Michel Habib, Christophe Paul
2001 B conf
On Subfamilies of AT-Free Graphs.
WG
Ekkehard Köhler, Derek G. Corneil, Stephan Olariu, Lorna Stewart
2001 B conf
On the Relationship between Clique-Width and Treewidth.
WG
Derek G. Corneil, Udi Rotics
2001 J jnl
Stable 2-pairs and (
Discret. Math.
Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski
2000 J jnl
Pancyclicity and NP-completeness in Planar Graphs.
Discret. Appl. Math.
Mingchu Li, Derek G. Corneil, Eric Mendelsohn
2000 B conf
Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract).
LATIN
Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, Udi Rotics
1999 A* conf
LBFS Orderings and Cocomparability Graphs.
SODA
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1999 J jnl
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs.
SIAM J. Comput.
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1998 J jnl
Characterization and parameterized generation of synthetic combinational benchmark circuits.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
Michael D. Hutton, Jonathan Rose, Jerry P. Grossman, Derek G. Corneil
1998 J jnl
Completeness for intersection classes.
Discret. Math.
Timothy B. Moorhouse, Derek G. Corneil
1998 B conf
Diameter Determination on Restricted Graph Faminlies.
WG
Derek G. Corneil, Feodor F. Dragan, Michel Habib, Christophe Paul
1998 A* conf
The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract).
SODA
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1998 J jnl
The existence of uniquely -G colourable graphs.
Discret. Math.
Dimitris Achlioptas, Jason I. Brown, Derek G. Corneil, Michael Molloy
1998 J jnl
Tree Powers.
J. Algorithms
Paul E. Kearney, Derek G. Corneil
1997 J jnl
Asteroidal Triple-Free Graphs.
SIAM J. Discret. Math.
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1997 A conf
Generation of Synthetic Sequential Benchmark Circuits.
FPGA
Michael D. Hutton, Jonathan Rose, Derek G. Corneil
1996 J jnl
A generalization of line graphs: (
J. Graph Theory
Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski
1996 J jnl
A generalization of perfect graphs -
J. Graph Theory
Leizhen Cai, Derek G. Corneil
1996 A* conf
Characterization and Parameterized Random Generation of Digital Circuits.
DAC
Michael D. Hutton, Jerry P. Grossman, Jonathan Rose, Derek G. Corneil
1996 J jnl
on the Structure of Trapezoid Graphs.
Discret. Appl. Math.
F. Cheah, Derek G. Corneil
1995 J jnl
A Linear Time Algorithm to Compute a Dominating Path in an AT-Free Graph.
Inf. Process. Lett.
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1995 B conf
Computing a Dominating Pair in an Asteroidal Triple-free Graph in Linear Time.
WADS
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1995 J jnl
Isomorphic Tree Spanner Problems.
Algorithmica
Leizhen Cai, Derek G. Corneil
1995 A* conf
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs.
ICALP
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1995 J jnl
Negative Results on Characterizing Visibility Graphs.
Comput. Geom.
Hazel Everett, Derek G. Corneil
1995 J jnl
Simple Linear Time Recognition of Unit Interval Graphs.
Inf. Process. Lett.
Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague
1995 J jnl
Tree Spanners.
SIAM J. Discret. Math.
Leizhen Cai, Derek G. Corneil
1994 J jnl
Edge-disjoint packings of graphs.
Discret. Appl. Math.
Derek G. Corneil, Shigeru Masuyama, S. Louis Hakimi
1993 B conf
Asteroidal Triple-Free Graphs.
WG
Derek G. Corneil, Stephan Olariu, Lorna Stewart
1993 J jnl
On the Complexity of the Embedding Problem for Hypercube Related Graphs.
Discret. Appl. Math.
Alan Wagner, Derek G. Corneil
1993 J jnl
Polynomial-time Instances of the Minimum Weight Triangulation Problem.
Comput. Geom.
Efthymios Anagnostou, Derek G. Corneil
1993 J jnl
Stable Set Bonding in Perfect Graphs and Parity Graphs.
J. Comb. Theory B
Derek G. Corneil, Jean Fonlupt
1992 J jnl
On cycle double covers of line graphs.
Discret. Math.
Leizhen Cai, Derek G. Corneil
1991 J jnl
Addendum.
Discret. Appl. Math.
F. Cheah, Derek G. Corneil
1991 J jnl
Graph properties and hypergraph colourings.
Discret. Math.
Jason I. Brown, Derek G. Corneil
1991 J jnl
Parallel Algorithms for Parity Graphs.
J. Algorithms
Teresa M. Przytycka, Derek G. Corneil
1990 J jnl
A note on
J. Graph Theory
Jason I. Brown, Derek G. Corneil, Ali Ridha Mahjoub
1990 J jnl
Dominating sets in perfect graphs.
Discret. Math.
Derek G. Corneil, Lorna K. Stewart
1990 J jnl
Embedding Trees in a Hypercube is NP-Complete.
SIAM J. Comput.
Alan Wagner, Derek G. Corneil
1990 J jnl
Forbidden minors characterization of partial 3-trees.
Discret. Math.
Stefan Arnborg, Andrzej Proskurowski, Derek G. Corneil
1990 J jnl
Recognizing Visibility Graphs of Spiral Polygons.
J. Algorithms
Hazel Everett, Derek G. Corneil
1990 J jnl
The complexity of regular subgraph recognition.
Discret. Appl. Math.
F. Cheah, Derek G. Corneil
1989 J jnl
The complexity of generalized clique covering.
Discret. Appl. Math.
Derek G. Corneil, Jean Fonlupt
1987 J jnl
On generalized graph colorings.
J. Graph Theory
Jason I. Brown, Derek G. Corneil
1986 J jnl
Families of graphs complete for the strong perfect graph Conjecture.
J. Graph Theory
Derek G. Corneil
1986 J jnl
K
Discret. Math.
Michele Conforti, Derek G. Corneil, Ali Ridha Mahjoub
1985 J jnl
A Linear Recognition Algorithm for Cographs.
SIAM J. Comput.
Derek G. Corneil, Yehoshua Perl, Lorna K. Stewart
1985 J jnl
The complexity of generalized clique packing.
Discret. Appl. Math.
Derek G. Corneil
1984 J jnl
A Non-Factorial Algorithm for Canonical Numbering of a Graph.
J. Algorithms
Derek G. Corneil, Mark K. Goldberg
1984 J jnl
Clustering and domination in perfect graphs.
Discret. Appl. Math.
Derek G. Corneil, Yehoshua Perl
1983 J jnl
A note on a conjecture by Gavril on clique separable graphs.
Discret. Math.
Derek G. Corneil, J. Mark Keil
1983 J jnl
On pseudosimilarity in trees.
J. Comb. Theory B
David G. Kirkpatrick, Maria M. Klawe, Derek G. Corneil
1981 J jnl
Complement reducible graphs.
Discret. Appl. Math.
Derek G. Corneil, H. Lerchs, L. Stewart Burlingham
1981 J jnl
Forest embeddings in regular graphs of large girth.
J. Comb. Theory B
David G. Kirkpatrick, Derek G. Corneil
1980 J jnl
A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem.
SIAM J. Comput.
Derek G. Corneil, David G. Kirkpatrick
1980 J jnl
On deciding switching equivalence of graphs.
Discret. Appl. Math.
Charles J. Colbourn, Derek G. Corneil
1978 J jnl
Parallel Computations in Graph Theory.
SIAM J. Comput.
Eshrat Reghbati, Derek G. Corneil
1977 J jnl
The graph isomorphism disease.
J. Graph Theory
Ronald C. Read, Derek G. Corneil
1975 A* conf
Parallel Computations in Graph Theory
FOCS
Eshrat Arjomandi, Derek G. Corneil
1973 J jnl
An Algorithm for Determining the Chromatic Number of a Graph.
SIAM J. Comput.
Derek G. Corneil, Bruce Graham
1973 J jnl
Minimal Event-Node Network of Project Precedence Relations.
Commun. ACM
Derek G. Corneil, C. C. Gotlieb, Y. M. Lee
1972 J jnl
Corrections to Bierstone's Algorithm for Generating Cliques.
J. ACM
Gordon D. Mulligan, Derek G. Corneil
1971 J jnl
An n² Algorithm for Determining the Bridges of a Graph.
Inf. Process. Lett.
Derek G. Corneil
1970 J jnl
An Efficient Algorithm for Graph Isomorphism.
J. ACM
Derek G. Corneil, C. C. Gotlieb
1970 J jnl
The syllabus for the 1970 University of Toronto Ph. D. written comprehensive examination.
ACM SIGCSE Bull.
Derek G. Corneil
1967 J jnl
Algorithms for finding a fundamental set of cycles for an undirected linear graph.
Commun. ACM
C. C. Gotlieb, Derek G. Corneil