A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
type: Item
instance of: scholarly article
title: A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
zbMATH Open document ID: 0633.05039
DOI: 10.1016/0166-218X(86)90036-3
author: E. Balas
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The author gives an O(\(\Delta| E|)\) algorithm (\(\Delta\) denotes the maximum degree) for the construction of edge maximal subgraph G' of a given graph G with the property that there exists an edge 2-coloring of G' such that one color induces a triangulated subgraph of G' while the complementary color induces a subgraph of G' without triangles. These researches have applications in maximum clique finding enumerative algorithms.
reviewed by: Mirko Křivánek
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4029609
zbMATH Keywords: triangulated graph
zbMATH Keywords: algorithm
zbMATH Keywords: edge maximal subgraph
zbMATH Keywords: edge 2-coloring
zbMATH Keywords: maximum clique
MaRDI profile type: Publication
cites work: On the Maximum Weight Clique Problem
cites work: Finding a Maximum Clique in an Arbitrary Graph
cites work: Maximal chordal subgraphs
cites work: On rigid circuit graphs
cites work: Q3328583
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
full work available at URL: 0166-218x(86)90036-3
OpenAlex ID: W2030774898
description: scientific article; zbMATH DE number 4029609