Accession Number : ADA308575

Title :   Intersection Graphs and Geometric/Combinatorial Optimization.

Descriptive Note : Final rept. Jul 85-Sep 94,

Corporate Author : JOHNS HOPKINS UNIV BALTIMORE MD DEPT OF MATHEMATICAL SCIENCES

Personal Author(s) : Scheinerman, Edward R.

PDF Url : ADA308575

Report Date : 13 MAY 1996

Pagination or Media Count : 8

Abstract : This project focused on the interaction between geometric objects and combinatorial structures, especially intersection graphs and containment orders. Let sigma denote a family of sets. We call a graph G a sigma-intersection graph provided there is a mapping f: V(G) right arrow sigma with the property that uv is in E(G) exactly when f(u) intersection f(v) not equal empty set. Similarly, we call a partially ordered set P a sigma-containment order provided there is a mapping f : P right arrow sigma so that x <= y exactly when f(x) is a subset contained in f(y). A second theme in the research was the use of random methods and the development of novel models and applications of random graphs, including intermingling the intersection and random graph paradigms.

Descriptors :   *GRAPHS, MATHEMATICAL MODELS, OPTIMIZATION, COMBINATORIAL ANALYSIS, RESEARCH MANAGEMENT, SET THEORY, MAPPING(TRANSFORMATIONS).

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE