๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The maximum k-colorable subgraph problem for chordal graphs

โœ Scribed by Mihalis Yannakakis; Fanica Gavril

Book ID
113163032
Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
390 KB
Volume
24
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A generalization of chordal graphs and t
A generalization of chordal graphs and the maximum clique problem
โœ Assef Chmeiss; Philippe Jรฉgou ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 584 KB

A graph is chordal or triangulated if it has no chordless cycle with four or more vertices. Chordal graphs are well known for their combinatorial and algorithmic properties. Here we introduce a generalization of chordal graphs, namely CSGk graphs. Informally, a CSG' graph is a complete graph, and fo

Tight Bounds for the Maximum Acyclic Sub
Tight Bounds for the Maximum Acyclic Subgraph Problem
โœ Bonnie Berger; Peter W Shor ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 209 KB

Given a directed graph G s V, A , the maximum acyclic subgraph problem is to ลฝ . find a maximum cardinality subset Aะˆ of the arcs such that Gะˆ s V, Aะˆ is acyclic. In this paper, we present polynomial-time and RNC algorithms which, when given ลฝ any graph G without two-cycles, find an acyclic subgraph