Joe Sawada
University of Toronto
Abstract:
A graph is strongly chordal if and only if it has a simple elimination
ordering (SEO) of its vertices. We focus on two interesting questions
about a strongly chordal graph G:
(1) How fast can we find an SEO of G?
(2) How fast can we list all SEOs of G?
Currently, strongly chordal graphs cannot be recognized in linear time - despite a recent claim to the contrary. We show that if we can find an SEO for G in linear time then we can also recognize strongly chordal graphs in linear time.
If there is time, we will discuss the second question. In particular, the set of all SEOs of a strongly chordal graph correspond to the basic words of a related antimatroid. By discovering a constant time transposition "oracle" we can use an existing Gray code algorithm to list all SEO's in constant amortized time.
Amram Meir
Department of Mathematics and Statistics
York University
Abstract: The nodes of every non-trivial tree can be partitioned into two classes, A and B, such that no two nodes of the same class are joined. Given a family F of trees , let Y(n,k) = Y(n,k; F) denote the number of trees T in F such that the classes A and B of T have k and n-k nodes , respectively; and let Y(n) denote the total number of trees T in F having n nodes. The ratios Y(n,k) / Y(n), and, in particular, the ratio r(n) =Y(n,n/2) / Y(n) for even values of n , are of interest.
Asymptotic results for Simply Generated families (including rooted labelled, binary, etc.) trees were obtained by us (1999), and for unlabelled-unrooted trees more recently by Pippenger (2001).
Here we consider the asymptotic behaviour of Y(n,k) / Y(n) for Recursive Trees.
This is joint work with J.W. Moon (University of Alberta).
Rudi Mathon
Department of Computer Science
University of Toronto
Abstract: A new algorithm will be described for finding subgraphs with a specified number of edges in a given graph. We employ a randomized strategy based on restricted local search.
The algorithm has been successfully tested to find
(i) maximum cliques in 3 classes of random graphs with up to
100000 vertices,
(ii) maximum independent sets in block intersection graphs
yielding Steiner t-designs
(iii) extremal regular subgraphs in strongly regular graphs
to be used as switching sets to new sr-graphs
(iv) subgraphs of a given size with the maximum number of
edges in random multigraphs of a given density with
applications to clustering analysis in networks and
systems.
Frank Ruskey
Department of Computer Science
University of Victoria
Abstract: Venn diagrams have long been used as an aid in understanding set containment relationships and in certain logical arguments. By extending in a natural way the familiar 3 circle Venn diagram interesting graph theoretic, combinatorial, and geometrical questions arise. This talk is a survey of what is known about Venn diagrams, particularly the aesthetic and extremal properties of the drawings, including recent results about symmetric and minimum area Venn diagrams. The talk is at the advanced undergraduate level and includes many beautiful illustrations. For more about Venn diagrams see http://www.theory.cs.uvic.ca/~cos/venn.
Contact: fruskey at csr.uvic.ca
Stephen Olariu
Old Dominion University
Abstract: TBA
Mohammad Salavatipour
Department of Computer Science
University of Toronto
Abstract: The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph $G$ that connect a given set of required points $S$. This problem is motivated by practical applications in VLSI-layout and broadcasting, as well as theoretical reasons. In this paper, we study this problem and present an algorithm with an asymptotic approximation factor of $|S|/4$. This gives a sufficient condition for the existence of $k$ edge-disjoint Steiner trees in a graph in terms of the edge-connectivity of the graph. We will show that this condition is the best possible if the number of terminals is 3. At the end, we consider the fractional version of this problem, and observe that it can be reduced to the minimum Steiner tree problem via the ellipsoid algorithm.
This is joint work with Kamal Jain (Microsoft Research) and Mohammad Mahdian (CS Lab, MIT) to appear in SODA 2003.
Olivier Dubois
Universite de Paris IV
Abstract: (tentative)
In this paper, he and J. Mandler determine the precise
value of the 3-XOR-SAT threshold. I.e., they determine
a constant t, such that a uniformly random instance of 3-XOR-SAT
on n variables and cn clauses is almost surely satisfiable
for c<t and is almost surely unsatisfiable for c>t.
Robert Jamison
Department of Mathematical Sciences
Clemson University
Abstract: An isomorphic factorization of a graph $G=(V,E)$ is a partition of the edge set $E$ into parts which determine isomorphic subgraphs of $G$. It is often convenient to think of the parts of the partition as color classes of edges. Thus one can also speak of an isomorphic factorization of $G$ into $k$ parts as an isomorphic $k$-coloring of $G$. We also say that a graph $G$ $k$-splits if it has an isomorphic $k$-coloring
An obvious necessary condition, called the Divisibility Condition,
for a graph $G$ to $k$-split is that $k$ divides the number
of edges $e(G)$ of $G$.
Under certain circumstances, this simple condition is also sufficient.
This is the case
1) for certain regular graphs, including the complete graphs,
2) when $e(G) = 2k$,
and 3) when $k \ge \chi'(G)$, the edge chromatic number of $G$.
This talk will focus on non-obvious necessary conditions for certain classes of caterpillars (trees obtained by adding a collection of ``hairs'' to a path ``spine'') to $k$-split. In particular, a complete analysis will be given for several types of caterpillar, where the necessary and sufficient conditions are seen to be number-theoretic in nature.
Contact: rejam at clemson.edu
Gerald Penn
Department of Computer Science
University of Toronto
Abstract: The Lambek calculus is a substructural logic, lacking the classical rules of weakening, exchange, and permutation. We will consider the question:
"Is the sequent A1...An |- B derivable in the Lambek Calculus?"
where A1,...,An,B are (possibly implicational) types. In computational linguistics, these types are syntactic categories assigned to words by a lexicon. Given an LCG, G, and a string w1...wn, with unique types, A1...An, given by G's lexicon, this amounts to string recognition when B=s (sentence), the distinguished category of G. Although the string languages recognisable by LCGs are known to be weakly equivalent to the context-free languages, no polynomial-time decision procedure for this question is known.
This talk seeks to contribute to this issue by presenting a simple graph-theoretic construction for representing the well-formedness constraints of an LCG derivation, reminiscent of Girard's (1987) "long trip condition" for proof nets in linear logic. An algorithm resembling a standard CFG chart-parser is also provided for answering the above sequent derivability question. Crucially, this algorithm takes exponential time in the worst case, so it does not put the matter to rest.
By contrast, much of the recent work on parsing with LCGs has chosen to dwell on elegant implementations of LCG proof search in higher-order logic programming languages. While these are indeed elegant, they are perhaps not the best choice for discovering the complexity of the problem at hand. It is for this reason that we opt for a ``back-to-basics'' approach, using only a few simple algorithms and basic graph theory to characterise the problem. Given our extensive knowledge about algorithmic efficiency and NP-completeness in the domain of graph theory, it is hoped either that the algorithm given here can be enhanced and proven to be polynomial, or that a failure to so enhance it will reveal an embedding of a known NP-hard problem into LCG recognition.
Christophe Paul
LIRMM, Montpellier
Abstract: The central question we are interested in is: "How to encode information about a graph in such a way that an oracle is able to answer queries on that graph?"
Queries can deal with such issues as adjacency, connectivity, distances in graphs and comparability, least common ancestors in posets. There are various types of representations such as centralized or distributed. As usual, we have to deal with the tradeoff between time and space: time for the query answer, space for the size of the encoding.
After presenting general considerations on graph representations, we will talk about results on encodings that enable the oracle to answer queries about distances, namely a "distance labeling scheme". Various schemes for a number of graph classes will be presented.
|
|