Title page for ETD etd-1107103-233833

Type of Document Dissertation
Author Kandara, Osman
Author's Email Address okanda1@lsu.edu
URN etd-1107103-233833
Title Level of Essentialness of a Node in Flowcharts and Its Application to Program Testing
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
S. Kundu Committee Chair
D. Carver Committee Member
E. Kennedy Committee Member
J. Chen Committee Member
D. Rinks Dean's Representative
  • flowchart analysis
  • debugging
  • program slicing
  • regression testing
  • node coverage
  • path coverage
  • selecting test cases
  • cyclomatic complexity
  • software engineering
  • domination
  • domination tree
  • post-domination
  • post domination
  • post-domination tree
  • post domination tree
  • essential set
  • white box testing
  • software testing
  • black box testing
  • path testing
  • data flow testing
  • loop testing
  • code inspection
  • condition testing
Date of Defense 2003-11-04
Availability unrestricted
Program testing is important to develop bug free software. A common form of program testing involves selecting test cases which execute (cover) a given set W of statements in the program. In regression testing, W typically forms a small subset of the program. It is often possible to find an alternate small set W so that execution of W' implies execution of W.

We develop concepts and algorithms for finding W' as small as possible with the condition that the statements in W' are "close" to those in W in terms of program structure. These concepts generalize the notion of the essential set, which was introduced by Bertolino for the special case W= set of all program statements.

We define the essential-for relationship between two nodes x and y and degree of essentialness for a node x in a program flowchart. The sets Ei = all nodes whose degrees of essentialness is the ith largest value, i.e., ith level essential nodes form a partition. We group them in a certain way to form the sets Gj so that each Gj "covers" G1, G2, , Gj-1. The sets Gj are then pruned by using a suitable notion of "equivalence" to form the sets Hi, which have two important properties: Hi covers Hi-1 and |Hi| ≥ |Hi-1|. The sets Hi are then used to construct our desired set W'.

We give efficient algorithms to compute the sets Hi and the set W' and illustrate our method with example programs.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Kandara_dis.pdf 1.30 Mb 00:06:00 00:03:05 00:02:42 00:01:21 00:00:06

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.