Accession Number:

ADA232901

Title:

An Algorithm to Find a K5 Minor

Descriptive Note:

Technical rept.

Corporate Author:

ILLINOIS UNIV AT URBANA COLL OF ENGINEERING

Report Date:

1991-02-01

Pagination or Media Count:

29.0

Abstract:

We present an On squared algorithm that, given a graph, either returns a K sub 5 minor or reports that no such minor exists. The algorithm exploits a characterization of graphs containing no K sub 5 minor that is similar to Wagners characterization.

Descriptors:

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE