Certifying algorithms

DOI10.1016/j.cosrev.2010.09.009zbMath1298.68289OpenAlexW55887128MaRDI QIDQ465678

Kurt Mehlhorn, Ross M. McConnell, Pascal Schweitzer, Stefan Näher

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2010.09.009

zbMATH Keywords

software reliability certification certifying algorithms

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) General topics in the theory of algorithms (68W01)

Related Items

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency, Colouring graphs with no induced six-vertex path or diamond, A proof system for graph (non)-isomorphism verification, Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, Cyclability in graph classes, λ > 4, Well-partitioned chordal graphs, Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs, Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection, Linear-time recognition of map graphs with outerplanar witness, Essential obstacles to Helly circular-arc graphs, Efficiently correcting matrix products, On the speed of constraint propagation and the time complexity of arc consistency testing, Efficiently Correcting Matrix Products, Fair Division of Indivisible Goods for a Class of Concave Valuations, Certifying coloring algorithms for graphs without long induced paths, Analyzing read-once cutting plane proofs in Horn systems, Recognizing union-find trees is NP-complete, A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs, Certifying induced subgraphs in large graphs, A tie-break model for graph search, What's decidable about discrete linear dynamical systems?, Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs, A simple certifying algorithm for 3-edge-connectivity, On certifying distributed algorithms: problem of local correctness, Unnamed Item, QMaxSATpb: a certified MaxSAT solver, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms, A certifying and dynamic algorithm for the recognition of proper circular-arc graphs, Edge-orders, Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge, Certifying 3-edge-connectivity, Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance, A combinatorial certifying algorithm for linear feasibility in UTVPI constraints, Recognition of split-graphic sequences, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, Unnamed Item, Computing vertex-disjoint paths in large graphs using MAOs, Functional Encryption for Inner Product with Full Function Privacy, Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info, Dynamic Dominators and Low-High Orders in DAGs, On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems, On fair division for indivisible items, Trustworthy Graph Algorithms (Invited Talk), Colouring graphs with no induced six-vertex path or diamond, Mondshein Sequences (a.k.a. (2,1)-Orders), A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING THE RESILIENCE OF ARRANGEMENTS OF RAY SENSORS, Discovering and certifying lower bounds for the online bin stretching problem, Unnamed Item, On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, Cogent: uniqueness types and certifying compilation, Fully dynamic recognition of proper circular-arc graphs, A framework for the verification of certifying computations, Algebraic model checking for discrete linear dynamical systems, Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Uses Software

Cites Work