Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_2003_e.pdf164.pdf
View attachments here: