An O(/V/+/E/) Algorithm for finding an Edge-Maximal Subgraph with a TR-Formative Coloring.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Theoretical Mathematics