Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSohler, Christian-
dc.contributor.authorFichtenberger, Hendrik-
dc.date.accessioned2020-07-10T05:44:34Z-
dc.date.available2020-07-10T05:44:34Z-
dc.date.issued2020-
dc.identifier.urihttp://hdl.handle.net/2003/39198-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-21116-
dc.description.abstractProperty testing considers decision problems in the regime of sublinear complexity. Most classical decision problems require at least linear time complexity in order to read the whole input. Hence, decision problems are relaxed by introducing a gap between “yes” and “no” instances: A property tester for a property Π (e. g., planarity) is a randomized algorithm with constant error probability that accepts objects that have Π (planar graphs) and that rejects objects that have linear edit distance to any object from Π (graphs with a linear number of crossing edges in every planar embedding). For property testers, locality is a natural and crucial concept because they cannot obtain a global view of their input. In this thesis, we investigate property testing in graphs and how testers leverage the information contained in the neighborhoods of randomly sampled vertices: We provide some structural insights regarding properties with constant testing complexity in graphs with bounded (maximum vertex) degree and a connection between testers with constant complexity for general graphs and testers with logarithmic space complexity for random-order streams. We also present testers for some minor-freeness properties and a tester for conductance in the distributed CONGEST model.en
dc.language.isoende
dc.subjectProperty testingen
dc.subjectSublinear algorithmsen
dc.subjectGraph algorithmsen
dc.subject.ddc004-
dc.titleProperty testing of graphs and the role of neighborhood distributionsen
dc.typeTextde
dc.contributor.refereeCzumaj, Artur-
dc.date.accepted2020-02-11-
dc.type.publicationtypedoctoralThesisde
dc.subject.rswkGraphentheoriede
dcterms.accessRightsopen access-
eldorado.secondarypublicationfalsede
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
fichtenberger-phd_thesis.pdfDNB1.23 MBAdobe PDFView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org