检索结果-内蒙古大学图书馆

certifying algorithms for recognizing interval graphs and permutation graphs

SIAM JOURNAL ON COMPUTING 2006年第2期36卷 326-353页

作者： Kratsch, Dieter McConnell, Ross M. Mehlhorn, Kurt Spinrad, Jeremy P. Univ Metz LITA F-57045 Metz 01 France Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA Max Planck Inst Informat D-66123 Saarbrucken Germany Vanderbilt Univ Dept Elect Engn & Comp Sci Nashville TN 37235 USA

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.

关键词： certificates certifying algorithms interval graphs permutation graphs

来源：评论

学校读者我要写书评

暂无评论

Polynomial time certifying algorithms for the planar quantified integer programming problem

引用

JOURNAL OF LOGIC AND COMPUTATION 2013年第5期23卷 1017-1033页

作者： Liang, Z. Subramani, K. Worthington, J. W Virginia Univ LCSEE Morgantown WV 26508 USA

This article is concerned with the design and analysis of polynomial time algorithms for determining whether a Planar Quantified Integer Program (PQIP) is feasible. A PQIP can be described briefly as an integer program involving two variables, in which each variable can be either universally or existentially quantified. There are four types of PQIPs, depending on how the variables are quantified (existentially or universally). In this article, we present two new, simple, and efficient algorithms for the for all there exists case as well as a detailed account of the complexity of the other cases. Moreover, we discuss certification with respect to the provided algorithms.

关键词： certifying algorithms polynomial time Quantified Integer Programs constraints lattice points

来源：评论

学校读者我要写书评

暂无评论

Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs

引用

APPLIED MATHEMATICS LETTERS 2011年第5期24卷 648-652页

作者： Hung, Ruo-Wei Chang, Maw-Shang Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 413 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan

关键词： certifying algorithms Path cover Hamiltonian cycle Interval graphs

来源：评论

学校读者我要写书评

暂无评论

An Introduction to certifying algorithms

引用

IT-INFORMATION TECHNOLOGY 2011年第6期53卷 287-293页

作者： Alkassar, Eyad Boehme, Sascha Mehlhorn, Kurt Rizkallah, Christine Schweitzer, Pascal Saarland Univ Campus 1 3 D-66123 Saarbrucken Germany Tech Univ Munich \ D-66132 Garching Germany Max Planck Inst Informat D-66132 Saarbrucken Germany Australian Natl Univ Canberra ACT 0200 Australia

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.

关键词： D.2.5 [Software: Software Engineering: Software/Program Verification] D.2.5 [Software: Software Engineering: Testing and Debugging] certifying algorithms

来源：评论

学校读者我要写书评

暂无评论

certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2005年第3期18卷 554-570页

作者： Hell, P Huang, J Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

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).

关键词： proper interval graphs proper interval bigraphs bipartite permutation graphs bipartite trapezoid graphs proper circular arc graphs lexicographic breadth first search recognition algorithms certifying algorithms forbidden subgraph characterizations

来源：评论

学校读者我要写书评

暂无评论

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第39期412卷 5351-5373页

作者： Hung, Ruo-Wei Chang, Maw-Shang Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 62102 Taiwan

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.

关键词： certifying algorithms Hamiltonian cycle Path cover Interval graphs Circular-arc graphs

来源：评论

学校读者我要写书评

暂无评论

An O(nm)-time certifying algorithm for recognizing HHD-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 452卷 117-131页

作者： Nikolopoulos, Stavros D. Palios, Leonidas Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

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.

关键词： HHD-free graphs Perfectly orderable graphs certifying algorithms Recognition

来源：评论

学校读者我要写书评

暂无评论

Discovering and certifying lower bounds for the online bin stretching problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 938卷 1-15页

作者： Bohm, Martin Simon, Bertrand Univ Wroclaw Inst Comp Sci Wroclaw Poland CNRS IN2P3 Comp Ctr Villeurbanne France

There are several problems in the theory of online computation where tight lower bounds on the competitive ratio are unknown and expected to be difficult to describe in a short form. A good example is the ONLINE BIN STRETCHING problem, in which the task is to pack the incoming items online into bins while minimizing the load of the largest bin. Additionally, the optimal load of the entire instance is known in advance. The contribution of this paper is twofold. We use the Coq proof assistant to formalize the ONLINE BIN STRETCHING problem and provide a program certifying lower bounds of this problem. Because of the size of the certificates, previously claimed lower bounds were never formally proven. To the best of our knowledge, this is the first use of a formal verification toolkit to certify a lower bound for an online problem. We also provide the first non-trivial lower bounds for ONLINE BIN STRETCHING with 6, 7 and 8 bins, and increase the best known lower bound for 3 bins. We describe in detail the algorithmic improvements which were necessary for the discovery of the new lower bounds, which are several orders of magnitude more complex.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Online bin stretching Online lower bound certifying algorithms Proof assistant

来源：评论

学校读者我要写书评

暂无评论

A Framework for the Verification of certifying Computations

引用

JOURNAL OF AUTOMATED REASONING 2014年第3期52卷 241-273页

作者： Alkassar, Eyad Boehme, Sascha Mehlhorn, Kurt Rizkallah, Christine Univ Saarland Fachbereich Informat Saarbrucken Germany Tech Univ Munich Inst Informat Garching Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

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.

关键词： Software verification certifying algorithms certifying computations Formal verification VCC Isabelle Interactive theorem proving Automatic code verification

来源：评论

学校读者我要写书评

暂无评论

An O(n plus m) certifying Triconnnectivity Algorithm for Hamiltonian Graphs

引用

ALGORITHMICA 2012年第3-4期62卷 754-766页

作者： Elmasry, Amr Mehlhorn, Kurt Schmidt, Jens M. MPI Informat D-66123 Saarbrucken Germany FU Berlin Dept Comp Sci Berlin Germany

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.

关键词： Graph algorithms certifying algorithms Triconnectivity Hamiltonian graph

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：