|
|||||
|
|
A one-to-one correspondence between colorings and stable sets |
|
| Authors: | Denis Cornaz Vincent Jost |
| Institution: | a LIMOS, Complexe scientifique des Cézeaux, 63177 Aubière cedex, France b ROSO - TRANSP-OR, EPFL - Lausanne, Switzerland |
| Abstract: | Given a graph G, we construct an auxiliary graph  with  vertices such that the set of all stable sets of  is in one-to-one correspondence with the set of all colorings of G. Then, we show that the Max-Coloring problem in G reduces to the Maximum Weighted Stable set problem in  . |
| Keywords: | Graph coloring Stable set Max-Coloring _method=retrieve& _eid=1-s2 0-S016763770800103X& _mathId=si16 gif& _pii=S016763770800103X& _issn=01676377& _acct=C000054348& _version=1& _userid=3837164& md5=5c631ab95262508e9947d1c1dc7fc81c')" style="cursor:pointer p-batch scheduling" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">p-batch scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ | |