Accession Number:

ADA170023

Title:

An O(/V/+/E/) Algorithm for finding an Edge-Maximal Subgraph with a TR-Formative Coloring.

Descriptive Note:

Management science research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1985-07-01

Pagination or Media Count:

18.0

Abstract:

If TR is the class of triangulated graphs, a TR-formative edge coloring is a greenred coloring of the edges of a graph, such that the green graph is triangulated i.e. belongs to TR and the red graph has no triangles. Recently Balas, Chvatal and Nesetril gave an 0 V to the 5th power algorithm for finding a maximum-weight clique in any graph G V,E with a known TR-formative edge coloring. In this paper we given an 0 V E time algorithm for finding in an arbitrary graph an edge-maximal subgraph with a TR-formative coloring. This can be used to construct improved implicit enumeration procedures for finding a maximum-weight clique in an arbitrary graph. The algorithm consists of two subroutines, also of interest in their own right one finds an edge-maximal triangulated subgraph, the other one an edge-maximal triangle-free subgraph, in an arbitrary graph. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE