MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kratsch, Dieter
McConnell, Ross
Mehlhorn, Kurt
Spinrad, Jeremy P.		dblp
dblp
dblp
dblp
Not MPG Author(s):
??
Editor(s):
BibTeX cite key*:
Kratsch-et-al:interval
Title, Booktitle
Title*:
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
Mehlhorn_a_2003_e.pdf (980.6 KB); 164.pdf (263.37 KB)
Booktitle*:
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
Event, URLs
Conference URL::
Downloading URL:
http://delivery.acm.org/10.1145/650000/644137/p158-kratsch.pdf?key1=644137&key2=5548797511&coll=GUIDE&dl=GUIDE&CFID=664222&CFTOKEN=65161800
Event Address*:
Baltimore, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
30 March 2005
Event End Date:
30 March 2005
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
158-167
Year*:
2003
VG Wort Pages:
ISBN/ISSN:
0-89871-538-5
Sequence Number:
DOI:
Note, Abstract, ©
Note:
Final version in SIAM J. Comput.
(LaTeX) Abstract:
A certifying algorithm for a decision 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. 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 non-membership can be authenticated in O(|V|) time.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kratsch-et-al:interval,
AUTHOR = {Kratsch, Dieter and McConnell, Ross and Mehlhorn, Kurt and Spinrad, Jeremy P.},
 TITLE = {Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs},
 BOOKTITLE = {Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)},
 PUBLISHER = {SIAM},
 YEAR = {2003},
 PAGES = {158--167},
 ADDRESS = {Baltimore, USA},
 ISBN = {0-89871-538-5},
 NOTE = {Final version in SIAM J. Comput.},
}

Entry last modified by Tamara Hausmann, 11/09/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Seth Pettie		Created
03/30/2005 11:12:27
Revisions
11.
10.
9.
8.
7.		Editor(s)
Tamara Hausmann
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
09.11.2006 14:41:03
04.10.2006 09:40:12
11.09.2006 15:42:17
11.09.2006 15:27:41
11.09.2006 15:26:10