Elek, Gábor (2022) Planarity can be verified by an approximate proof labeling scheme in constant-time. JOURNAL OF COMBINATORIAL THEORY SERIES A, 191. ISSN 0097-3165
|
Text
2006_11869v2.pdf Download (219kB) | Preview |
Abstract
Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry [3]. Roughly speaking, a graph property P can be verified by an approximate proof labeling scheme in constant-time if the vertices of a graph having the property can be convinced, in a short period of time not depending on the size of the graph, that they are having the property P or at least they are not far from being having the property P. The main result of this paper is that bounded-degree planar graphs (and also outer-planar graphs, bounded genus graphs, knotlessly embeddable graphs etc.) can be verified by an approximate proof labeling scheme in constant-time. © 2022 Elsevier Inc.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | approximate proof labeling schemes, planar graphs, Property A, hyperfiniteness |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 13 Mar 2023 15:09 |
Last Modified: | 06 Apr 2023 14:36 |
URI: | http://real.mtak.hu/id/eprint/162080 |
Actions (login required)
![]() |
Edit Item |