An Approach to Prove Correctness of Graph Algorithm
Published: 2012
Author(s) Name: Vinay Kumar
Locked
Subscribed
Available for All
Abstract
An algorithm is said to be correct if for every input data that
satisfies some conditions-called the precondition of the
algorithm, the output data satisfy a certain predefined
condition-called the post condition of the algorithm. A
graph algorithm depends upon number of nodes and edges
in a graph and inter/intra relationship between these two
features. In this paper an approach based on incremental
induction on edge or on node or on both is described to
mathematically prove or disprove the correctness of a
graph algorithm. This is required in view of the complex
nature of graph theory world and changing properties of
graph with changes in the number of nodes, edges and their
relations in the graph.
View PDF