default search action
Derek G. Corneil
Derek Gordon Corneil
Person information
- affiliation: University of Toronto, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j85]Jérémie Dusart, Michel Habib
, Derek G. Corneil:
Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications. Order 41(1): 99-133 (2024) - 2021
- [j84]Jérémie Dusart
Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. SIAM J. Comput. 50(3): 1148-1153 (2021) - 2020
- [j83]Derek G. Corneil, Robert Ganian, Andrzej Proskurowski:
Foreword: Eighth Workshop on Graph Classes, Optimization, and Width Parameters, Toronto, Ontario, Canada. Discret. Appl. Math. 278: 1-2 (2020)
2010 – 2019
- 2018
- [j82]Derek G. Corneil, Sang-il Oum, Christophe Paul:
Preface: Seventh Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015. Discret. Appl. Math. 248: 1-2 (2018) - 2016
- [j81]Derek G. Corneil, Jérémie Dusart, Michel Habib, Antoine Mamcarz, Fabien de Montgolfier:
A tie-break model for graph search. Discret. Appl. Math. 199: 89-100 (2016) - [j80]Derek G. Corneil, Jérémie Dusart, Michel Habib, Ekkehard Köhler:
On the Power of Graph Searching for Cocomparability Graphs. SIAM J. Discret. Math. 30(1): 569-591 (2016) - [r1]Derek G. Corneil, Michel Habib:
Unified View of Graph Searching and LDFS-Based Certifying Algorithms. Encyclopedia of Algorithms 2016: 2291-2297 - [i7]Jérémie Dusart, Michel Habib
Maximal cliques structure for cocomparability graphs and applications. CoRR abs/1611.02002 (2016) - 2015
- [j79]Derek G. Corneil, Juraj Stacho:
Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number. J. Graph Theory 78(1): 61-79 (2015) - [i6]Derek G. Corneil, Jérémie Dusart, Michel Habib, Fabien de Montgolfier:
A tie-break model for graph search. CoRR abs/1501.06148 (2015) - 2014
- [j78]Emeric Gioan, Christophe Paul
Practical and Efficient Circle Graph Recognition. Algorithmica 69(4): 759-788 (2014) - [j77]Emeric Gioan, Christophe Paul
Practical and Efficient Split Decomposition via Graph-Labelled Trees. Algorithmica 69(4): 789-843 (2014) - 2013
- [j76]Derek G. Corneil, Barnaby Dalton, Michel Habib
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. SIAM J. Comput. 42(3): 792-807 (2013) - 2012
- [j75]Derek G. Corneil, Michel Habib
Polynomial-time recognition of clique-width ≤3 graphs. Discret. Appl. Math. 160(6): 834-865 (2012) - [j74]Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang:
Collective additive tree spanners for circle graphs and polygonal graphs. Discret. Appl. Math. 160(12): 1717-1729 (2012) - [j73]George B. Mertzios, Derek G. Corneil:
A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs. SIAM J. Discret. Math. 26(3): 940-963 (2012) - 2011
- [j72]George B. Mertzios, Derek G. Corneil:
Vertex splitting and the recognition of trapezoid graphs. Discret. Appl. Math. 159(11): 1131-1147 (2011) - [i5]Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil:
Practical and Efficient Split Decomposition via Graph-Labelled Trees. CoRR abs/1104.3283 (2011) - [i4]Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil:
Circle Graph Recognition in Time O(n+m) α(n+m). CoRR abs/1104.3284 (2011) - 2010
- [j71]Derek G. Corneil, Ekkehard Köhler, Jean-Marc Lanlignel:
On end-vertices of Lexicographic Breadth First Searches. Discret. Appl. Math. 158(5): 434-443 (2010) - [i3]George B. Mertzios, Derek G. Corneil:
A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs. CoRR abs/1004.4560 (2010)
2000 – 2009
- 2009
- [j70]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
The LBFS Structure and Recognition of Interval Graphs. SIAM J. Discret. Math. 23(4): 1905-1953 (2009) - 2008
- [j69]Derek G. Corneil, Richard Krueger:
A Unified View of Graph Searching. SIAM J. Discret. Math. 22(4): 1259-1276 (2008) - [j68]Anna Bretscher, Derek G. Corneil, Michel Habib, Christophe Paul
A Simple Linear Time LexBFS Cograph Recognition Algorithm. SIAM J. Discret. Math. 22(4): 1277-1296 (2008) - [c20]Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. ICALP (1) 2008: 634-645 - [c19]Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang:
Additive Spanners for Circle Graphs and Polygonal Graphs. WG 2008: 110-121 - 2007
- [c18]Marc Tedder, Derek G. Corneil:
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs. STACS 2007: 344-355 - [i2]Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul:
Simple, linear-time modular decomposition. CoRR abs/0710.3901 (2007) - 2006
- [j67]Natasa Przulj
Efficient estimation of graphlet frequency distributions in protein-protein interaction networks. Bioinform. 22(8): 974-980 (2006) - [j66]Feodor F. Dragan, Chenyu Yan, Derek G. Corneil:
Collective Tree Spanners and Routing in AT-free Related Graphs. J. Graph Algorithms Appl. 10(2): 97-122 (2006) - [j65]Derek G. Corneil, Ekkehard Köhler, Stephan Olariu, Lorna Stewart:
Linear Orderings of Subfamilies of AT-Free Graphs. SIAM J. Discret. Math. 20(1): 105-118 (2006) - 2005
- [j64]Natasa Przulj
2-Tree probe interval graphs have a large obstruction set. Discret. Appl. Math. 150(1-3): 216-231 (2005) - [j63]Derek G. Corneil, Richard Krueger:
Simple vertex ordering characterizations for graph search: (expanded abstract). Electron. Notes Discret. Math. 22: 445-449 (2005) - [j62]Derek G. Corneil, Udi Rotics:
On the Relationship Between Clique-Width and Treewidth. SIAM J. Comput. 34(4): 825-847 (2005) - [c17]Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan:
Collective Tree 1-Spanners for Interval Graphs. WG 2005: 151-162 - 2004
- [j61]Natasa Przulj
Modeling interactome: scale-free or geometric?. Bioinform. 20(18): 3508-3515 (2004) - [j60]Natasa Przulj
Hereditary dominating pair graphs. Discret. Appl. Math. 134(1-3): 239-261 (2004) - [j59]Derek G. Corneil:
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discret. Appl. Math. 138(3): 371-379 (2004) - [j58]Lap Chi Lau, Derek G. Corneil:
Recognizing Powers of Proper Interval, Split, and Chordal Graph. SIAM J. Discret. Math. 18(1): 83-102 (2004) - [c16]Derek G. Corneil:
Lexicographic Breadth First Search - A Survey. WG 2004: 1-19 - [c15]Feodor F. Dragan, Chenyu Yan, Derek G. Corneil:
Collective Tree Spanners and Routing in AT-free Related Graphs. WG 2004: 68-80 - [e1]Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, Jeremy P. Spinrad:
Robust and Approximative Algorithms an Particular Graph Classes, 23.05. - 28.05.2004. Dagstuhl Seminar Proceedings 04221, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2004 [contents] - [i1]Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, Jeremy P. Spinrad:
04221 Abstracts Collection - Robust and Approximative Algorithms on Particular Graph Classes. Robust and Approximative Algorithms an Particular Graph Classes 2004 - 2003
- [j57]Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler:
On the power of BFS to determine a graph's diameter. Networks 42(4): 209-222 (2003) - [c14]Anna Bretscher, Derek G. Corneil, Michel Habib
A Simple Linear Time LexBFS Cograph Recognition Algorithm. WG 2003: 119-130 - 2002
- [j56]Michael D. Hutton, Jonathan Rose, Derek G. Corneil:
Automatic generation of synthetic sequential benchmark circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 21(8): 928-940 (2002) - [c13]Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler:
On the Power of BFS to Determine a Graphs Diameter. LATIN 2002: 209-223 - 2001
- [j55]Derek G. Corneil, Feodor F. Dragan, Michel Habib
Diameter determination on restricted graph families. Discret. Appl. Math. 113(2-3): 143-166 (2001) - [j54]Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski:
Stable 2-pairs and (X, Y)-intersection graphs. Discret. Math. 230(1-3): 119-131 (2001) - [c12]Derek G. Corneil, Udi Rotics:
On the Relationship between Clique-Width and Treewidth. WG 2001: 78-90 - [c11]Ekkehard Köhler, Derek G. Corneil, Stephan Olariu, Lorna Stewart:
On Subfamilies of AT-Free Graphs. WG 2001: 241-253 - 2000
- [j53]Mingchu Li, Derek G. Corneil, Eric Mendelsohn:
Pancyclicity and NP-completeness in Planar Graphs. Discret. Appl. Math. 98(3): 219-225 (2000) - [c10]Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, Udi Rotics:
Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract). LATIN 2000: 126-134
1990 – 1999
- 1999
- [j52]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs. SIAM J. Comput. 28(4): 1284-1297 (1999) - [c9]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
LBFS Orderings and Cocomparability Graphs. SODA 1999: 883-884 - 1998
- [j51]Dimitris Achlioptas, Jason I. Brown
The existence of uniquely -G colourable graphs. Discret. Math. 179(1-3): 1-11 (1998) - [j50]Timothy B. Moorhouse, Derek G. Corneil:
Completeness for intersection classes. Discret. Math. 190(1-3): 277-286 (1998) - [j49]Paul E. Kearney, Derek G. Corneil:
Tree Powers. J. Algorithms 29(1): 111-131 (1998) - [j48]Michael D. Hutton, Jonathan Rose, Jerry P. Grossman, Derek G. Corneil:
Characterization and parameterized generation of synthetic combinational benchmark circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 17(10): 985-996 (1998) - [c8]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract). SODA 1998: 175-180 - [c7]Derek G. Corneil, Feodor F. Dragan, Michel Habib, Christophe Paul:
Diameter Determination on Restricted Graph Faminlies. WG 1998: 192-202 - 1997
- [j47]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Asteroidal Triple-Free Graphs. SIAM J. Discret. Math. 10(3): 399-430 (1997) - [c6]Michael D. Hutton, Jonathan Rose, Derek G. Corneil:
Generation of Synthetic Sequential Benchmark Circuits. FPGA 1997: 149-155 - 1996
- [j46]F. Cheah, Derek G. Corneil:
on the Structure of Trapezoid Graphs. Discret. Appl. Math. 66(2): 109-133 (1996) - [j45]Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski:
A generalization of line graphs: (X, Y)-intersection graphs. J. Graph Theory 21(3): 267-287 (1996) - [j44]Leizhen Cai, Derek G. Corneil:
A generalization of perfect graphs - i-perfect graphs. J. Graph Theory 23(1): 87-103 (1996) - [c5]Michael D. Hutton, Jerry P. Grossman, Jonathan Rose, Derek G. Corneil:
Characterization and Parameterized Random Generation of Digital Circuits. DAC 1996: 94-99 - 1995
- [j43]Leizhen Cai, Derek G. Corneil:
Isomorphic Tree Spanner Problems. Algorithmica 14(2): 138-153 (1995) - [j42]Hazel Everett, Derek G. Corneil:
Negative Results on Characterizing Visibility Graphs. Comput. Geom. 5: 51-63 (1995) - [j41]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
A Linear Time Algorithm to Compute a Dominating Path in an AT-Free Graph. Inf. Process. Lett. 54(5): 253-257 (1995) - [j40]Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague:
Simple Linear Time Recognition of Unit Interval Graphs. Inf. Process. Lett. 55(2): 99-104 (1995) - [j39]Leizhen Cai, Derek G. Corneil:
Tree Spanners. SIAM J. Discret. Math. 8(3): 359-387 (1995) - [c4]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs. ICALP 1995: 292-302 - [c3]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Computing a Dominating Pair in an Asteroidal Triple-free Graph in Linear Time. WADS 1995: 358-368 - 1994
- [j38]Derek G. Corneil, Shigeru Masuyama, S. Louis Hakimi:
Edge-disjoint packings of graphs. Discret. Appl. Math. 50(2): 135-148 (1994) - 1993
- [j37]Efthymios Anagnostou, Derek G. Corneil:
Polynomial-time Instances of the Minimum Weight Triangulation Problem. Comput. Geom. 3: 247-259 (1993) - [j36]Alan Wagner, Derek G. Corneil:
On the Complexity of the Embedding Problem for Hypercube Related Graphs. Discret. Appl. Math. 43(1): 75-95 (1993) - [j35]Derek G. Corneil, Jean Fonlupt:
Stable Set Bonding in Perfect Graphs and Parity Graphs. J. Comb. Theory B 59(1): 1-14 (1993) - [c2]Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Asteroidal Triple-Free Graphs. WG 1993: 211-224 - 1992
- [j34]Leizhen Cai, Derek G. Corneil:
On cycle double covers of line graphs. Discret. Math. 102(1): 103-106 (1992) - 1991
- [j33]F. Cheah, Derek G. Corneil:
Addendum. Discret. Appl. Math. 31(3): 309 (1991) - [j32]Jason I. Brown
Graph properties and hypergraph colourings. Discret. Math. 98(2): 81-93 (1991) - [j31]Teresa M. Przytycka, Derek G. Corneil:
Parallel Algorithms for Parity Graphs. J. Algorithms 12(1): 96-109 (1991) - 1990
- [j30]F. Cheah, Derek G. Corneil:
The complexity of regular subgraph recognition. Discret. Appl. Math. 27(1-2): 59-68 (1990) - [j29]Stefan Arnborg, Andrzej Proskurowski, Derek G. Corneil:
Forbidden minors characterization of partial 3-trees. Discret. Math. 80(1): 1-19 (1990) - [j28]Derek G. Corneil, Lorna K. Stewart:
Dominating sets in perfect graphs. Discret. Math. 86(1-3): 145-164 (1990) - [j27]Hazel Everett, Derek G. Corneil:
Recognizing Visibility Graphs of Spiral Polygons. J. Algorithms 11(1): 1-26 (1990) - [j26]Jason I. Brown
A note on Ki-perfect graphs. J. Graph Theory 14(3): 333-340 (1990) - [j25]Alan Wagner, Derek G. Corneil:
Embedding Trees in a Hypercube is NP-Complete. SIAM J. Comput. 19(3): 570-590 (1990)
1980 – 1989
- 1989
- [j24]Derek G. Corneil, Jean Fonlupt:
The complexity of generalized clique covering. Discret. Appl. Math. 22(2): 109-118 (1989) - 1987
- [j23]Jason I. Brown
On generalized graph colorings. J. Graph Theory 11(1): 87-99 (1987) - [j22]Michele Conforti, Derek Gordon Corneil, Ali Ridha Mahjoub:
Ki-covers. II. Ki-perfect graphs. J. Graph Theory 11(4): 569-584 (1987) - 1986
- [j21]Michele Conforti, Derek G. Corneil, Ali Ridha Mahjoub:
Ki-covers I: Complexity and polytopes. Discret. Math. 58(2): 121-142 (1986) - [j20]Derek G. Corneil:
Families of graphs complete for the strong perfect graph Conjecture. J. Graph Theory 10(1): 33-40 (1986) - 1985
- [j19]Derek G. Corneil:
The complexity of generalized clique packing. Discret. Appl. Math. 12(3): 233-239 (1985) - [j18]Derek G. Corneil, Yehoshua Perl, Lorna K. Stewart:
A Linear Recognition Algorithm for Cographs. SIAM J. Comput. 14(4): 926-934 (1985) - 1984
- [j17]Derek G. Corneil, Yehoshua Perl:
Clustering and domination in perfect graphs. Discret. Appl. Math. 9(1): 27-39 (1984) - [j16]Derek G. Corneil, Mark K. Goldberg:
A Non-Factorial Algorithm for Canonical Numbering of a Graph. J. Algorithms 5(3): 345-362 (1984) - 1983
- [j15]Derek G. Corneil, J. Mark Keil:
A note on a conjecture by Gavril on clique separable graphs. Discret. Math. 46(3): 317-318 (1983) - [j14]David G. Kirkpatrick, Maria M. Klawe, Derek G. Corneil:
On pseudosimilarity in trees. J. Comb. Theory B 34(3): 323-339 (1983) - 1981
- [j13]Derek G. Corneil, H. Lerchs, L. Stewart Burlingham:
Complement reducible graphs. Discret. Appl. Math. 3(3): 163-174 (1981) - [j12]David G. Kirkpatrick, Derek G. Corneil:
Forest embeddings in regular graphs of large girth. J. Comb. Theory B 30(1): 45-60 (1981) - 1980
- [j11]Charles J. Colbourn, Derek G. Corneil:
On deciding switching equivalence of graphs. Discret. Appl. Math. 2(3): 181-184 (1980) - [j10]Derek G. Corneil, David G. Kirkpatrick:
A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem. SIAM J. Comput. 9(2): 281-297 (1980)
1970 – 1979
- 1978
- [j9]Eshrat Reghbati, Derek G. Corneil:
Parallel Computations in Graph Theory. SIAM J. Comput. 7(2): 230-237 (1978) - 1977
- [j8]Ronald C. Read, Derek G. Corneil:
The graph isomorphism disease. J. Graph Theory 1(4): 339-363 (1977) - 1975
- [c1]Eshrat Arjomandi, Derek G. Corneil:
Parallel Computations in Graph Theory. FOCS 1975: 13-18 - 1973
- [j7]Derek G. Corneil, C. C. Gotlieb, Y. M. Lee:
Minimal Event-Node Network of Project Precedence Relations. Commun. ACM 16(5): 296-298 (1973) - [j6]Derek G. Corneil, Bruce Graham:
An Algorithm for Determining the Chromatic Number of a Graph. SIAM J. Comput. 2(4): 311-318 (1973) - 1972
- [j5]Gordon D. Mulligan, Derek G. Corneil:
Corrections to Bierstone's Algorithm for Generating Cliques. J. ACM 19(2): 244-247 (1972) - 1971
- [j4]Derek G. Corneil:
An n² Algorithm for Determining the Bridges of a Graph. Inf. Process. Lett. 1(2): 51-55 (1971) - 1970
- [j3]Derek G. Corneil, C. C. Gotlieb:
An Efficient Algorithm for Graph Isomorphism. J. ACM 17(1): 51-64 (1970) - [j2]Derek G. Corneil:
The syllabus for the 1970 University of Toronto Ph. D. written comprehensive examination. ACM SIGCSE Bull. 2(2): 41-43 (1970)
1960 – 1969
- 1967
- [j1]C. C. Gotlieb, Derek G. Corneil:
Algorithms for finding a fundamental set of cycles for an undirected linear graph. Commun. ACM 10(12): 780-783 (1967)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:07 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: