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

Abstract

If TR is the class of triangulated graphs, a TR-formative edge coloring is a green/red 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA170023

Entities

People

  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Construction
  • Contracts
  • Governments
  • Inclusions
  • Iterations
  • Mathematics
  • Military Research
  • Pennsylvania
  • Schools
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.