Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs

Kratsch, D., McConnell, R., Mehlhorn, K., & Spinrad, J. P. (2006). Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs. SIAM Journal on Computing, 36, 326-353.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-224D-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-224E-E
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kratsch, Dieter, Autor
McConnell, Ross, Autor
Mehlhorn, Kurt1, Autor           
Spinrad, Jeremy P., Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of nonmembership can be authenticated in O(|V|) time.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-09-132006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 314649
Anderer: Local-ID: C1256428004B93B8-90DAACD3D4A0C6A8C1256E20004505E1-mehlhorn06b
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: SIAM Journal on Computing
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 36 Artikelnummer: - Start- / Endseite: 326 - 353 Identifikator: ISSN: 0097-5397