التفاصيل البيبلوغرافية
| العنوان: |
A Heuristic for the Coloring of Planar Graphs. |
| المؤلفون: |
De Ita Luna, Guillermo, López-Ramírez, Cristina, De Ita-Varela, Ana E., Gutiérrez-Gómez, Jorge E. |
| المصدر: |
ENTCS: Electronic Notes in Theoretical Computer Science; Dec2020, Vol. 354, p91-105, 15p |
| مصطلحات موضوعية: |
GRAPH coloring, PLANAR graphs, INDEPENDENT sets, ODD numbers, ALGORITHMS |
| مستخلص: |
We present an algorithm for the coloring of planar graphs based on the construction of a maximal independent set S of the input graph. The maximal independent set S must fulfill certain characteristics. For example, S contains the vertex that appears in a maximum number of odd cycles of G. The construction of S considers the internal-face graph of the input graph G in order to select each vertex belonging to a maximal number of odd faces of G. The traversing in pre-order on the internal-face graph G f of the input planar graph G provides us of a strategy for the construction of partial maximal independent sets of critical regions of G f. Thus, the union of these partial maximal independent sets forms a maximal independent set S of G. This allows us to color first the vertices that are crucial for decomposing G in a graph (G − S), which is a polygonal tree, and therefore, is 3-colorable. [ABSTRACT FROM AUTHOR] |
|
Copyright of ENTCS: Electronic Notes in Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |
Full Text Finder