Atlas Mathematical Conference Abstracts || Conferences | Abstracts | for Organizers | About AMCA

Horizons in Combinatorics/16th Shanks Lecture Series
May 21-24, 2001
Vanderbilt University
Nashville, TN, USA

Organizers
Paul Edelman, Mark Ellingham, Jonathan Farley, Mike Plummer, Jerry Spinrad

View Abstracts
Conference Homepage

Fast recognition of classes of partial cubes
by
Wilfried Imrich
Montanuniversität Leoben, A-8700 Leoben, Austria
Coauthors: Bostjan Bresar, Sandi Klavzar (University of Maribor, 2000 Maribor, Slovenia)

Isometric subgraphs of hypercubes, are a rich class of graphs that includes median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This talk is concerned with classes of partial cubes that are not median graphs but can be recognized in O(mlogn) steps.

Date received: April 20, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cags-71.