Graph Minors: Structure Theory and Algorithms

Abstract

There have been significant developments in Graph Theory over the last decade that imply the existence of polynomial time algorithms for a large class of problems. These results, however, guarantee the existence of polynomial-time algorithms to solve various problems, but give no hint how to find one. Yet another drawback of these algorithms is that even though they are theoretically fast (O(n2) or O(n3)), the constant hidden in the 0 notation is so enormous that it makes the algorithms impractical. The purpose of this project is to (1) further develop this theory and obtain more theoretical results, (2) apply these results to the design of (at least theoretically) efficient algorithms, and (3) turn these theoretically efficient algorithms into practical ones.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1993
Accession Number
ADA271851

Entities

People

  • Robin Thomas

Organizations

  • Georgia Tech

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programs
  • Computers
  • Contracts
  • Decomposition
  • Embedding
  • Graph Theory
  • Guarantees
  • Notation
  • Polynomials
  • Prototypes
  • Scientists
  • Students
  • Universities

Fields of Study

  • Computer science

Readers

  • Educational Psychology
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.