Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Kratsch, Dieter
McConnell, Ross
Mehlhorn, Kurt
Spinrad, Jeremy P.

dblp
dblp
dblp
dblp

Not MPG Author(s):

Kratsch, Dieter
McConnell, Ross
Spinrad, Jeremy P.

BibTeX cite key*:

mehlhorn06b

Title

Title*:

Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:


Publisher's
Address:

Philadelphia, PA, USA

ISSN:

0097-5397

Vol, No, pp, Date

Volume*:

36

Number:

2

Publishing Date:

2006

Pages*:

326-353

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1137/S0097539703437855

Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://portal.acm.org/citation.cfm?id=1139977&coll=GUIDE&dl=GUIDE&CFID=664222&CFTOKEN=65161800#
http://dx.doi.org/10.1137/S0097539703437855

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{mehlhorn06b,
AUTHOR = {Kratsch, Dieter and McConnell, Ross and Mehlhorn, Kurt and Spinrad, Jeremy P.},
TITLE = {Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs},
BOOKTITLE = {Siam Journal on Computing},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2006},
ORGANIZATION = {ACM},
NUMBER = {2},
VOLUME = {36},
PAGES = {326--353},
ADDRESS = {Baltimore, USA},
ISBN = {0097-5397},
DOI = {10.1137/S0097539703437855},
}


Entry last modified by Anja Becker, 01/07/2008
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)
Petra Mayer
Created
01/19/2004 01:33:54 PM
Revisions
15.
14.
13.
12.
11.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
07.01.2008 09:45:30
13.09.2006 12:59:55
11.09.2006 15:40:44
11.09.2006 15:40:12
11.09.2006 15:32:50