A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hami...
详细信息
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. This paper presents O(n)-time certifying algorithms for the above two problems on interval graphs given a set of n intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in O(n) time. (C) 2010 Elsevier Ltd. All rights reserved.
A certifying algorithm is an algorithm that produces, with each output, a certificate or witness that the particular output is correct. A user of a certifying algorithm inputs x, receives the output y and the certific...
详细信息
A certifying algorithm is an algorithm that produces, with each output, a certificate or witness that the particular output is correct. A user of a certifying algorithm inputs x, receives the output y and the certificate w, and then checks, either manually or by use of a program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust the algorithm. We put forward the thesis that certifying algorithms are much superior to non- certifying algorithms, and that for complex algorithmic tasks, only certifying algorithms are satisfactory. Acceptance of this thesis would lead to a change of how algorithms are taught and how algorithms are researched. The widespread use of certifying algorithms would greatly enhance the reliability of algorithmic software. We also demonstrate that the formal verification of result checkers is within the reach of current verification technology. The combination of certifying algorithms and formal verification of result checkers leads to formally verified computations.
We report work-in-progress on applying the concept of a certifying algorithm to distributed algorithms. A certifying algorithm produces not only a result, but also a witness that verifies the result's correctness....
详细信息
ISBN:
(数字)9783319229690
ISBN:
(纸本)9783319229690;9783319229683
We report work-in-progress on applying the concept of a certifying algorithm to distributed algorithms. A certifying algorithm produces not only a result, but also a witness that verifies the result's correctness. certifying variants of numerous (sequential) algorithms have been developed. However, distributed algorithms behave differently from sequential algorithms. Consequently, it is challenging to make them certifying. Our local approach is to make the distributed algorithm compute many local witnesses that together verify the result's correctness. We identified problems for which this approach is applicable. Particularly, we hypothesize that for problems with optimal substructure (i.e., an optimal solution can be constructed from optimal solutions of its sub-problems) it is often easy to apply the local approach. As an example, we give a certifying distributed algorithm for the shortest path problem.
Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current automatic verification tools and usually involves intricate mathematical theorems. ...
详细信息
Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current automatic verification tools and usually involves intricate mathematical theorems. certifying algorithms compute in addition to each output a witness certifying that the output is correct. A checker for such a witness is usually much simpler than the original algorithm-yet it is all the user has to trust. The verification of checkers is feasible with current tools and leads to computations that can be completely trusted. We describe a framework to seamlessly verify certifying computations. We use the automatic verifier VCC for establishing the correctness of the checker and the interactive theorem prover Isabelle/HOL for high-level mathematical properties of algorithms. We demonstrate the effectiveness of our approach by presenting the verification of typical examples of the industrial-level and widespread algorithmic library LEDA.
In this paper, we consider the recognition problem on a class of perfectly orderable graphs, namely, the HHD-free graphs;such graphs do not contain any induced subgraph isomorphic to a house, a hole, or a domino. We p...
详细信息
In this paper, we consider the recognition problem on a class of perfectly orderable graphs, namely, the HHD-free graphs;such graphs do not contain any induced subgraph isomorphic to a house, a hole, or a domino. We prove properties of the HHD-free graphs which enable us to present an O(n m)-time and O(n + m)-space algorithm for determining whether a graph on n vertices and m edges is HHD-free;currently, this is the fastest algorithm for this problem. We also describe how the algorithm can be augmented to provide a certificate (an induced house, hole, or domino) whenever it decides that the input graph is not HHD-free, thus answering an open question posed by Hong and Sritharan (Theoretical Computer Science 259 (2001) 233-244). The certificate computation requires O(n + m) additional time and O(n) space. (C) 2012 Elsevier B.V. All rights reserved.
A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with...
详细信息
A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hami...
详细信息
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n(2) log n)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n(2) log n)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n(2) log n) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Delta n)-time certifying algorithm to solve this problem, where Delta represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time. (C) 2011 Elsevier B.V. All rights reserved.
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 ...
详细信息
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(vertical bar V vertical bar) time.
This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or ...
详细信息
This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated;otherwise, a certificate is returned within the same complexity. (c) 2006 Elsevier B.V. All rights reserved.
Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifyi...
详细信息
Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m+n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n).
暂无评论