О новых алгоритмических приемах для задачи о взвешенной вершинной раскраске
The Independent Set Problem for planar graphs is known to be NP-complete. In this paper, its polynomial solvability for some subclasses of planar graphs is proved.
When a society needs to take a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is manipulation. We say a voting rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by misrepresenting his or her preferences. The popular approach to comparing manipulability of voting rules is defining complexity class of the corresponding manipulation problem. This paper provides a survey into manipulation complexity literature considering variety of problems with different assumptions and restrictions.