Gur Saran Adhar
January 6, 1994
Description of Proposed Activity:
I plan to focus on two scholarly activities: (a). complete research on
new algorithm for ''domination in Tolerance Graphs''
(b). write users manual for design tools to be used by
students in csc242 and csc442 courses.
Preperation for undertaking the project:
For the activity (a). I have studied the background papers
for tolerance graphs [1]-[7]. My study of these graphs
reveal that their complements are special types of comparability
graphs and have a very elegant structure [1]. It means that
even though the known algorithms for the general class of co-comparability
graphs can be used to resolve problems arising in tolerance graphs
a clever design of data structures and algorithms will result in
much more efficient algorithms for tolerance graphs in particular.
This problem is significant since the solution of the
domination problem for the general
class of co-comparability graphs is very inefficient (requires
O(n6) time to solve for a graph with n vertices).
It is further noted that interval graphs are co-comparability graphs of
interval dimension `one' (also known as interval order)
whereas tolerance graphs are
co-comparability graphs with interval dimension `two'.
I have successfully solved the domination problem for interval graphs
and therefore I feel optimistic about the outcome of the proposed research
for the more general class.
During Fall'94 semester I would like to complete the research
and write the results for publication.
For the activity (b). I plan to introduce design tools to csc242 and csc442 courses during Spring 94 semester on a limited basis. The tools will be fully integrated into the courses once we have sufficient number of design workstations. A grant proposal requesting design stations has been submitted to NSF.
Potential benefit to the Department / University:
The results of the work under activity (a).
will be published in refereed journals
and presented in conference. A departmental seminar on the subject
will stimulate interest among graduate students and faculty interested
in the area of discrete mathematics, particularly among faculty interested in
graph theory, combinatorics and optimization.
Preparing users manual (activity-b) for design tools is essential to allow ease of use for the students. The manuals for the design tools provided by vendors are too detailed for effective use in the courses. Integration of design tools into csc242 and csc442 courses will significantly improve the quality of instruction in these courses.
REFERENCES
[1]. Tolerance Graphs and Orders, Stefan Felsner,
Tech. Report 309-1991, Technische Universitat Berlin.
[2]. Stability Number and Chromatic Number of Tolerance Graphs,
G. Narasimhan and Rachel Manber,
Tech. Report 1988, Comp. Sc. Dept., Univ. of Wisconsin-Madison.
[3]. The Predecessor Successor Relation and a Recognition
Algorithm for Orders of Dimension Two,
Larry J. Langley,
Tech. Report PMA-TR92-102,
Dartmouth College.
[4]. Proper and UNit Tolerance Graphs,
K.P. Bogart, G. Issak, L. Langley, and P.C. Fishburn,
DIMACS Tech. Report 91-74, DIMACS.
[5]. Bipartite Tolerance Orders,
K. P. Bogart, and Ann. N. Trenk,
Tech. Report 1992, Dartmouth College.
[6]. Tolerance Graphs,
M.C. Golumbic, C.L. Monma, and W.T. Trotter,
Discrete Applied Math. (1984) 157-170.
[7]. On Realizable Biorders and the Biorder Dimension of a relation,
J. P. Doignon, A. Duycamp, and J. C. Falmagne,
Jor. of Mathematical Psychology 28, 73-109 (1984).
[8]. Interval orders and Interval graphs, Peter C. Fishburn, Wiley-Interscience Series in Discrete Mathematics.