An Algorithm to Find a K5 Minor

Abstract

We present an O(n 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 Wagner's characterization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1991
Accession Number
ADA232901

Entities

People

  • Andre E. Kezdy
  • Patrick J. Mcguinness

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Acquisition
  • Algorithms
  • Classification
  • Computer Science
  • Contracts
  • Crossings
  • Iterations
  • Mathematics
  • Military Research
  • Notation
  • Observation
  • Polynomials
  • Procurement
  • Security
  • Universities