Derek G. Corneil

Order, April, 2024

2021

Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

2020

Foreword: Eighth Workshop on Graph Classes, Optimization, and Width Parameters, Toronto, Ontario, Canada.

[BibT_eX]

[DOI]

Robert Ganian

Discret. Appl. Math., 2020

2018

Preface: Seventh Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015.

[BibT_eX]

[DOI]

Sang-il Oum

Christophe Paul

Discret. Appl. Math., 2018

2016

Unified View of Graph Searching and LDFS-Based Certifying Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

On the Power of Graph Searching for Cocomparability Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

A tie-break model for graph search.

[BibT_eX]

[DOI]

Fabien de Montgolfier

Discret. Appl. Math., 2016

Maximal cliques structure for cocomparability graphs and applications.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number.

[BibT_eX]

[DOI]

Juraj Stacho

J. Graph Theory, 2015

A tie-break model for graph search.

[BibT_eX]

[DOI]

Fabien de Montgolfier

CoRR, 2015

2014

Practical and Efficient Split Decomposition via Graph-Labelled Trees.

[BibT_eX]

[DOI]

Algorithmica, 2014

Practical and Efficient Circle Graph Recognition.

[BibT_eX]

[DOI]

Algorithmica, 2014

2013

LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.

[BibT_eX]

[DOI]

Barnaby Dalton

SIAM J. Comput., 2013

2012

A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs.

[BibT_eX]

[DOI]

George B. Mertzios

SIAM J. Discret. Math., 2012

Collective additive tree spanners for circle graphs and polygonal graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

Polynomial-time recognition of clique-width ≤3 graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

2011

Vertex splitting and the recognition of trapezoid graphs.

[BibT_eX]

[DOI]

George B. Mertzios

Discret. Appl. Math., 2011

Circle Graph Recognition in Time O(n+m) α(n+m)

[BibT_eX]

[DOI]

CoRR, 2011

2010

On end-vertices of Lexicographic Breadth First Searches.

[BibT_eX]

[DOI]

Jean-Marc Lanlignel

Discret. Appl. Math., 2010

2009

The LBFS Structure and Recognition of Interval Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

2008

A Unified View of Graph Searching.

[BibT_eX]

[DOI]

Richard Krueger

SIAM J. Discret. Math., 2008

Additive Spanners for Circle Graphs and Polygonal Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Simple, linear-time modular decomposition

[BibT_eX]

[DOI]

CoRR, 2007

An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs.

[BibT_eX]

[DOI]

Marc Tedder

Proceedings of the STACS 2007, 2007

2006

Linear Orderings of Subfamilies of AT-Free Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Efficient estimation of graphlet frequency distributions in protein-protein interaction networks.

[BibT_eX]

[DOI]

Igor Jurisica

Bioinform., 2006

2005

Simple vertex ordering characterizations for graph search: (expanded abstract).

[BibT_eX]

[DOI]

Richard Krueger

Electron. Notes Discret. Math., 2005

2-Tree probe interval graphs have a large obstruction set.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

Collective Tree 1-Spanners for Interval Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

2004

Recognizing Powers of Proper Interval, Split, and Chordal Graph.

[BibT_eX]

[DOI]

Lap Chi Lau

SIAM J. Discret. Math., 2004

Hereditary dominating pair graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

Modeling interactome: scale-free or geometric?.

[BibT_eX]

[DOI]

Igor Jurisica

Bioinform., 2004

Collective Tree Spanners and Routing in AT-free Related Graphs.

[BibT_eX]

[DOI]

Feodor F. Dragan

Chenyu Yan

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Lexicographic Breadth First Search - A Survey.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

04221 Abstracts Collection - Robust and Approximative Algorithms on Particular Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the Robust and Approximative Algorithms an Particular Graph Classes, 23.05., 2004

2003

On the power of BFS to determine a graph's diameter.

[BibT_eX]

[DOI]

Feodor F. Dragan

Networks, 2003

A Simple Linear Time LexBFS Cograph Recognition Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

2002

Automatic generation of synthetic sequential benchmark circuits.

[BibT_eX]

[DOI]

Michael D. Hutton

Jonathan Rose

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2002

On the Power of BFS to Determine a Graphs Diameter.

[BibT_eX]

[DOI]

Feodor F. Dragan

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001

Stable 2-pairs and (X, Y)-intersection graphs.

[BibT_eX]

[DOI]

Discret. Math., 2001

Diameter determination on restricted graph families.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2001

On Subfamilies of AT-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

On the Relationship between Clique-Width and Treewidth.

[BibT_eX]

[DOI]

Udi Rotics

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

2000

Pancyclicity and NP-completeness in Planar Graphs.

[BibT_eX]

[DOI]

Mingchu Li

Eric Mendelsohn

Discret. Appl. Math., 2000

Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999

LBFS Orderings and Cocomparability Graphs.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Characterization and parameterized generation of synthetic combinational benchmark circuits.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1998

Tree Powers.

[BibT_eX]

[DOI]

Paul E. Kearney

J. Algorithms, 1998

Completeness for intersection classes.

[BibT_eX]

[DOI]

Timothy B. Moorhouse

Discret. Math., 1998

The existence of uniquely -G colourable graphs.

[BibT_eX]

[DOI]

Discret. Math., 1998

Diameter Determination on Restricted Graph Faminlies.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997

Generation of Synthetic Sequential Benchmark Circuits.

[BibT_eX]

[DOI]

Michael D. Hutton

Jonathan Rose

Proceedings of the 1997 ACM/SIGDA Fifth International Symposium on Field Programmable Gate Arrays, 1997

1996

A generalization of line graphs: (X, Y)-intersection graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 1996

A generalization of perfect graphs - i-perfect graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 1996

on the Structure of Trapezoid Graphs.

[BibT_eX]

[DOI]

F. Cheah

Discret. Appl. Math., 1996

Characterization and Parameterized Random Generation of Digital Circuits.

[BibT_eX]

[DOI]

Proceedings of the 33st Conference on Design Automation, 1996

1995

Tree Spanners.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1995

A Linear Time Algorithm to Compute a Dominating Path in an AT-Free Graph.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

Simple Linear Time Recognition of Unit Interval Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

Negative Results on Characterizing Visibility Graphs.

[BibT_eX]

[DOI]

Hazel Everett

Comput. Geom., 1995

Isomorphic Tree Spanner Problems.

[BibT_eX]

[DOI]

Algorithmica, 1995

Computing a Dominating Pair in an Asteroidal Triple-free Graph in Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

Edge-disjoint packings of graphs.

[BibT_eX]

[DOI]

Shigeru Masuyama

S. Louis Hakimi

Discret. Appl. Math., 1994

1993

Stable Set Bonding in Perfect Graphs and Parity Graphs.

[BibT_eX]

[DOI]

Jean Fonlupt

J. Comb. Theory B, 1993

On the Complexity of the Embedding Problem for Hypercube Related Graphs.

[BibT_eX]

[DOI]

Alan Wagner

Discret. Appl. Math., 1993

Polynomial-time Instances of the Minimum Weight Triangulation Problem.

[BibT_eX]

[DOI]

Efthymios Anagnostou

Comput. Geom., 1993

Asteroidal Triple-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

1992

On cycle double covers of line graphs.

[BibT_eX]

[DOI]

Discret. Math., 1992

1991

Parallel Algorithms for Parity Graphs.

[BibT_eX]

[DOI]

Teresa M. Przytycka

J. Algorithms, 1991

Graph properties and hypergraph colourings.

[BibT_eX]

[DOI]

Jason I. Brown

Discret. Math., 1991

Addendum.

[BibT_eX]

[DOI]

F. Cheah

Discret. Appl. Math., 1991

1990

Embedding Trees in a Hypercube is NP-Complete.

[BibT_eX]

[DOI]

Alan Wagner

SIAM J. Comput., 1990

A note on Ki-perfect graphs.

[BibT_eX]

[DOI]

Jason I. Brown

Ali Ridha Mahjoub

J. Graph Theory, 1990

Recognizing Visibility Graphs of Spiral Polygons.

[BibT_eX]

[DOI]

Hazel Everett

J. Algorithms, 1990

Dominating sets in perfect graphs.

[BibT_eX]

[DOI]

Lorna K. Stewart

Discret. Math., 1990

Forbidden minors characterization of partial 3-trees.

[BibT_eX]

[DOI]

Stefan Arnborg

Discret. Math., 1990

The complexity of regular subgraph recognition.

[BibT_eX]

[DOI]

F. Cheah

Discret. Appl. Math., 1990

1989

The complexity of generalized clique covering.

[BibT_eX]

[DOI]

Jean Fonlupt

Discret. Appl. Math., 1989

1987

Ki-covers. II. Ki-perfect graphs.

[BibT_eX]

[DOI]

Michele Conforti

Derek Gordon Corneil

Ali Ridha Mahjoub

J. Graph Theory, 1987

On generalized graph colorings.

[BibT_eX]

[DOI]

Jason I. Brown

J. Graph Theory, 1987

1986

Families of graphs complete for the strong perfect graph Conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 1986

Ki-covers I: Complexity and polytopes.

[BibT_eX]

[DOI]

Michele Conforti

Ali Ridha Mahjoub

Discret. Math., 1986

1985

A Linear Recognition Algorithm for Cographs.

[BibT_eX]

[DOI]

Yehoshua Perl

Lorna K. Stewart

SIAM J. Comput., 1985

The complexity of generalized clique packing.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1985

1984

A Non-Factorial Algorithm for Canonical Numbering of a Graph.

[BibT_eX]

[DOI]

Mark K. Goldberg

J. Algorithms, 1984

Clustering and domination in perfect graphs.

[BibT_eX]

[DOI]

Yehoshua Perl

Discret. Appl. Math., 1984

1983

On pseudosimilarity in trees.

[BibT_eX]

[DOI]

David G. Kirkpatrick

Maria M. Klawe

J. Comb. Theory B, 1983

A note on a conjecture by Gavril on clique separable graphs.

[BibT_eX]

[DOI]

J. Mark Keil

Discret. Math., 1983

1981

Forest embeddings in regular graphs of large girth.

[BibT_eX]

[DOI]

David G. Kirkpatrick

J. Comb. Theory B, 1981

Complement reducible graphs.

[BibT_eX]

[DOI]

H. Lerchs

L. Stewart Burlingham

Discret. Appl. Math., 1981

1980

A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem.

[BibT_eX]

[DOI]

David G. Kirkpatrick

SIAM J. Comput., 1980

On deciding switching equivalence of graphs.

[BibT_eX]

[DOI]

Charles J. Colbourn

Discret. Appl. Math., 1980

1978

Parallel Computations in Graph Theory.

[BibT_eX]

[DOI]

Eshrat Reghbati

SIAM J. Comput., 1978

1977

The graph isomorphism disease.

[BibT_eX]

[DOI]

Ronald C. Read

J. Graph Theory, 1977

1975

Parallel Computations in Graph Theory

[BibT_eX]

[DOI]

Eshrat Arjomandi

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1973

An Algorithm for Determining the Chromatic Number of a Graph.

[BibT_eX]

[DOI]

Bruce Graham

SIAM J. Comput., 1973

Minimal Event-Node Network of Project Precedence Relations.

[BibT_eX]

[DOI]

C. C. Gotlieb

Y. M. Lee

Commun. ACM, 1973

1972

Corrections to Bierstone's Algorithm for Generating Cliques.

[BibT_eX]

[DOI]

Gordon D. Mulligan

J. ACM, 1972

1971

An n² Algorithm for Determining the Bridges of a Graph.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1971

1970

The syllabus for the 1970 University of Toronto Ph. D. written comprehensive examination.

[BibT_eX]

[DOI]

ACM SIGCSE Bull., 1970

An Efficient Algorithm for Graph Isomorphism.

[BibT_eX]

[DOI]

C. C. Gotlieb

J. ACM, 1970

1967

Algorithms for finding a fundamental set of cycles for an undirected linear graph.

[BibT_eX]

[DOI]

C. C. Gotlieb