𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the Cornaz–Jost transformation to solve the graph coloring problem

✍ Scribed by Bonomo, Flavia; Giandomenico, Monia; Rossi, Fabrizio

Book ID
123007134
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
186 KB
Volume
113
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on the complexity of longest path
A note on the complexity of longest path problems related to graph coloring
✍ P.M. Pardalos; A. Migdalas 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 194 KB

In this note, we show that some problems related to the length of the longest simple path from a given vertex in a graph are NP-complete. We also discuss an extension to the graph coloring problem.

A note on the bottleneck graph partition
A note on the bottleneck graph partition problem
✍ Klinz, Bettina; Woeginger, Gerhard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 47 KB 👁 2 views

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem wit