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.
展开▼
机译：用于决策问题的认证算法是一种为证书提供所产生的每个答案的算法。该证书是证明答案未因实施中的错误而受到影响的证据。我们提供了线性时间证明算法来识别区间图和置换图。先前的算法声称输入图不是该类的成员时，无法提供支持证据。我们证明了我们的非会员证书可以在 O （＆verbar; V ＆verbar;）时间进行身份验证。
展开▼
