PDF

Mixed Graph Colorings: A Historical Review

Yuri N. Sotskov

2020Englishgraph coloringmixed graphschromatic numberedge coloringschedulingcomputational complexity

Abstract

Language:

This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices of the mixed graph and one coloring of the arcs and edges of the mixed graph have been considered in the literature. The unit-time scheduling problem with the makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of used colors is minimum. Complexity results for optimal colorings of the mixed graph are systematized. The published algorithms for finding optimal mixed graph colorings are briefly surveyed. Two new colorings of a mixed graph are introduced.

Download

Cite This Work

@article{51ed44b3-2600-4fb0-8931-9c228e8b7855,
  title={Mixed Graph Colorings: A Historical Review},
  author={Yuri N. Sotskov},
  year={2020},
  language={English}
}
TY  - JOUR
TI  - Mixed Graph Colorings: A Historical Review
AU  - Yuri N. Sotskov
PY  - 2020
LA  - English
ER  -

Similar Items

INGENIER´IA E INVESTIGACI ´ON VOL. 41 NO. 1, APRIL - 2021 (e84162)

Osvaldo Pavez, Pablo Herrera

Copper slag flotation was studied on an industrial scale at a concentrator plant in the region of Atacama, Chile. This study consisted of the physical

2021EnglishPDF

This is an electronic reprint of the original article.

Pekka Taskinen, Ari Jokilaakso

The effectivity of present copper smelting technologies have their roots in industrial and laboratory-scale experience accumulated over the past decad

2019EnglishPDF

Primary Copper Smelter and Refinery as a Recycling Plant—A System Integrated Approach to Estimate Secondary Raw Material Tolerance "2279

Olof Forsén, Jari Aromaa

The primary production of sulfide concentrates includes smelting to copper matte or blister copper, conversion of matte to blister copper, and refinin

2017EnglishPDF

Precious Metal Distributions Between Copper Matte and Slag at High in WEEE Reprocessing

Min Chen, Katri Avarmaa

The distributions of precious metals (gold, silver, platinum, and palladium) between copper matte and silica-saturated FeOx-SiO2/FeOx-SiO2-Al2O3/FeOx-

2021EnglishPDF

Precious metal recoveries in secondary copper smelting with high-alumina slags

Katri Avarmaa, Hugh O’Brien

Waste electrical and electronic equipment (WEEE) represents a significant urban resource for precious metals. To maximize the recoveries and sustainab

2020EnglishPDF

Data-Driven Power Electronic Converter Modeling

Nischal Guruwacharya, Niranjan Bhujel

A significant amount of converter-based generation is being integrated into the bulk electric power grid to fulfill the future electric demand through

2018EnglishPDF