|
|||||
|
|
A polynomial-time algorithm for near-unanimity graphs |
|
| Authors: | Benoit Larose, Cynthia Loten,L szl Z dori |
| Affiliation: | a Department of Mathematics and Statistics, Concordia University, 1455 de Maisonneuve West, Montréal, Qc, Canada, H3G 1M8;b Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, B.C., Canada, V5A 1S6;c Bolyai Intézet, Aradi vértanúk tere 1, H-6720, Szeged, Hungary |
| Abstract: | We present a simple polynomial-time algorithm that recognises reflexive, symmetric graphs admitting a near-unanimity operation. Several other characterisations of these graphs are also presented. |
| Keywords: | Near-unanimity operation Reflexive graph Polynomial-time algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |