Maximum Independent Sets in Subcubic Graphs: New Results

Autor:	Harutyunyan, Ararat, Lampis, Michael, Lozin, Vadim, Monnot, Jérôme
Rok vydání:	2018
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1810.10940 Zobrazit plný text záznamu View this record from Arxiv