|
The Department of Computer Science Colloquium Series is generally scheduled for 3:45 p.m. - 5:00 p.m. on
Wednesdays or Fridays, in the Math & Computer Science Building, Room 228.
Directions to our building are available.
The Department of Computer Science maintains a mailing list for colloquia announcements. If you are interested in receiving
emails when a colloquium is scheduled, please subscribe to the CS Colloquium Mailing List.
You may unsubscribe at any time.
Colloquium for Wednesday, April 15, 2009
| Speaker: |
Dr. R. Sritharan, Department of Computer Science, The University of Dayton, Dayton, Ohio
|
| Title: |
Graph sandwich problems
|
| Abstract: |
Given graphs G' = (V, E') and G'' = (V, E'') with E'
subset E'' and property P, the sandwich problem for property
P asks "Is there a graph G = (V, E) with E' subset E
subset E'' such that G has property P?". Intuitively,
the question asks if there is a graph G "in between" the graphs
G' and G'' such that G has the desired property P. It is
easily seen that when G' = G'', the problem reduces to the
recognition problem for property P (which asks if a given graph
G has property P). Thus, the sandwich problem for property
P is a generalization of the recognition problem for property
P.
The sandwich problem was introduced by Golumbic, Kaplan, and Shamir
in their paper published in Journal of Algorithms in 1995. In
this paper, Golumbic et al. established the computational complexity
of the sandwich problem for a variety of properties. They also left
the complexity of three problems as open questions. Two of these are
the sandwich problems for strongly chordal graphs and chordal
bipartite graphs.
Recently, we (with de Figueiredo, Faria, and Klein) showed that the
sandwich problem for strongly chordal graphs is NP-complete.
Subsequent to this, we have shown that the sandwich problem for
chordal bipartite graphs is also NP-complete.
In this talk, we survey results on sandwich problems and discuss
some related issues.
About the speaker:
R. Sritharan received his Ph.D in Computer Science from Vanderbilt
University in 1995. He is currently with the Computer Science
Department at The University of Dayton. His research interests are
in graph algorithms and algorithmic graph theory.
http://homepages.udayton.edu/~srithara/
Hosts: Feodor F. Dragan
|
| Time: |
Wednesday, April 15, 2009, 3:45 - 5:00 PM
|
| Place: |
MSB, Room 228
|
 |
Other Colloquia Scheduled for Spring 2009
| |
| |
| |
| |
- Wednesday April 1, 2009
Computational Thinking
Dr. Jeannette M. Wing, President's Professor of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Assistant Director, CISE Directorate, National Science Foundation
3:45 - 5:00 PM MSB, Room 228
|
| |
| |
| |
Return to Current Colloquia
|
