QP-2011-07

NP-hardness of the Clar number in general plane graphs

Attila Bernáth, Erika Bérczi-Kovács



Abstract

We prove that calculating the Clar number in general plane graphs is NP-hard.


Bibtex entry:

@techreport{egresqp-11-07,
AUTHOR = {Bern{\'a}th, Attila and B{\'e}rczi-Kov{\'a}cs, Erika},
TITLE = {NP-hardness of the Clar number in general plane graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {QP-2011-07}
}


Last modification: 16.10.2019. Please email your comments to Tamás Király!