A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring

DOI10.1016/0166-218X(86)90036-3zbMath0633.05039OpenAlexW2030774898MaRDI QIDQ1095923

Egon Balas

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90036-3

zbMATH Keywords

algorithmmaximum cliquetriangulated graphedge 2-coloringedge maximal subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimal triangulations of graphs: a survey ⋮ A vertex incremental approach for maintaining chordality ⋮ Maximal chordal subgraphs ⋮ Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring ⋮ Maximal sub-triangulation in pre-processing phylogenetic data ⋮ An algorithm for finding a maximum clique in a graph ⋮ The maximum clique problem

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Maximal chordal subgraphs
• Finding a Maximum Clique in an Arbitrary Graph
• On the Maximum Weight Clique Problem
• Algorithmic Aspects of Vertex Elimination on Graphs