A Partial Ordering of the Chordal Graphs.

Abstract

The chordal graphs have been well-studied because of their desirable algorithmic characteristics. Many problems that are intractable in the general case are solvable by fast algorithms in the chordal case. We show that the chordal graphs are partially ordered under edge set inclusion, and describe algorithms for bidirectional traversal of maximal chains in the corresponding cover graph. We also describe the embedding of several subclasses of the chordal graphs as subposets of the chordal poset, and suggest application of these order relations to the design of improved heuristics for obtaining approximate solutions to problems on arbitrary graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 07, 1997
Accession Number
ADA322752

Entities

People

  • Criag W. Rasmussen
  • Thomas J Carroll

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Elimination
  • Embedding
  • Genetic Algorithms
  • Graph Theory
  • Inclusions
  • Information Science
  • Intervals
  • Linear Algebra
  • Mathematical Models
  • Mathematics
  • Military Research
  • Schools
  • Sequences
  • Technical Information Centers

Readers

  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.