5799851
Universal Graphs for Bounded-Degree Trees and Planar Graphs
How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha \frac{1}{2}$.
33484235
Symmetries in Data Graphs
Data graphs were introduced as a vehicle for studying uniformities in the structure of graphs underlying data structures. This paper is devoted to investigating symmetries in data graphs. Such symmetries are of no little significance in every phase of the computational process. They can often be exploited to formulate more efficient algorithms, to simplify the specification of these algorithms, and to facilitate analysis of the resulting programs. The main thrust of this paper is to investigate the influence of various structural features of data graphs on the types of symmetries the data graphs enjoy what features ensure the presence of symmetries of various types, and what features limit the possible types of symmetries. These questions are studied first on the class of all data graphs, and then on the class of addressable (= realizable by relative addressing) data graphs.
849245
Story Segmentation of Broadcast News in English, Mandarin and Arabic
In this paper, we present results from a Broadcast News story segmentation system developed for the SRI NIGHTINGALE system operating on English, Arabic and Mandarin news shows to provide input to subsequent question-answering processes. Using a rule-induction algorithm with automatically extracted acoustic and lexical features, we report success rates that are competitive with state-of-the-art systems on each input language. We further demonstrate that features useful for English and Mandarin are not discriminative for Arabic.