40600226
The Complexity of Generalized Graph Colorings
Given a graph property P and positive integer k, a P k-coloring of a graph G is an assignment of one of k colors to each vertex of the graph so that the subgraphs induced by each color class have property P. This notion generalizes the standard definition of graph coloring, and has been investigated for many properties. We consider here the complexity of the decision problem. In particular, for the property —G, of not containing an induced subgraph isomorphic to G, we conjecture (and provide strong evidence) that —G k-colorability is NP-complete whenever G has order at least 3 and k ⩾ 2. The techniques rely on new NP-completeness results for hypergraph colorings.
14976506
Average independence polynomials
The independence polynomial of a graph G is the function i(G, x) = Σ k ≥ 0 ik xk, where ik is the number of independent sets of vertices in G of cardinality k. We investigate here the average independence polynomial, where the average is taken over all independence polynomials of (labeled) graphs of order n. We prove that while almost every independence polynomial has a nonreal root, the average independence polynomials always have all real, simple roots.
5392880
On chromatic roots with negative real part
19128559
Bounding the Roots of Independence Polynomials
2327812
The existence of uniquely -G colourable graphs
Abstract Given graphs F and G and a nonnegative integer k , a function π : V ( F ) → 1, …, k is a − G k-colouring of F if no induced copy of is monochromatic; F is − G k-chromatic if F has a − G k -colouring but no − G ( k − 1)-colouring. Further, we say F is uniquely − G k -colourable if F is − G k -chromatic and, up to a permutation of colours, it has only one − G k -colouring. Such notions are extensions of the well-known corresponding definitions from chromatic theory. It was conjectured that for all graphs G of order at least two and all positive integers k there exist uniquely − G k -colourable graphs. We prove the conjecture and show that, in fact, in all cases infinitely many such graphs exist.
28649866
A ramsey type problem concerning vertex colourings
Abstract Let H → k v G denote the fact that for every function π: V ( H ) → {1, …, k } there is an induced subgraph G ′ of H with G ′ ≅ G and V ( G ′) ⊆ π −1 ( i ) for some i . Folkman has shown that for all graphs G and for all positive integers k such a graph H exists. We examine here f ( G , k ), the minimum order of a graph H for which H → k v G . We show that for any fixed integer k ≥ 2 there are positive constants C 1 and C 2 such that C 1 n 2 ≤ max{ f ( G , k ): | V ( G )| = n } ≤ C 2 n 2 log 2 n .
267100
Proximity-aware directory-based coherence for multi-core processor architectures
As the number of cores increases on chip multiprocessors, coherence is fast becoming a central issue for multi-core performance. This is exacerbated by the fact that interconnection speeds are not scaling well with technology. This paper describes mechanisms to accelerate coherence for a multi-core architecture that has multiple private L2 caches and a scalable point-to-point interconnect between cores. These techniques exploit the differences in geometry between chip multiprocessors and traditional multiprocessor architectures.
 Directory-based protocols have been proposed as a scalable alternative to snoop-based protocols. In this paper, we discuss implementations of coherence for CMPs and propose and evaluate a novel directory-based coherence scheme to improve the performance of parallel programs on such processors. Proximity-aware coherence accelerates read and write misses by initiating cache-to-cache transfers from the spatially closest sharer. This has the dual benefit of eliminating unnecessary accesses to off-chip memory, and minimizing the distance over which communicated data moves across the network. The proposed schemes result in speedups up to 74.9% for our workloads.
5703219
A Macintosh Hypercard compilation of small subunit ribosomal RNA sequences
Molecular biologists, particularly those working with unicellular organisms, are becoming increasingly aware of the importance of understanding the phylogenetic (evolutionary) relationships between their model systems and other organisms. Currently, the best method for determining quantitatively the phylogenetic relationships in a group of organisms is the analysis of small subunit ribosomal RNA (ssu RNA) sequences (Woese, 1984). To assist in this type of analysis, the Ribosomal RNA Database Project (RDP) collects and distributes ssu rRNA sequences and software for phylogenetic analysis (Olsen et al., 1991). The ssu rRNA sequence stack is collection of almost 500 aligned ssu rRNA sequences taken from the first public release of the RDP sequence collection. The ssu rRNA sequence stack consists of a series of 'cards' each containing the ssu rRNA sequence of a single organism (Figure 1), from which the sequence can be copied (either with or without alignment information) or saved as a text file in GenBank format. Navigation in the stack is via a series of linked phylogenetic trees. Starting with a 'universal tree', clicking on the branch of interest takes the user to increasingly more specific and detailed trees. In the most specific trees, clicking on a branch either takes the user directly to the sequence card (if only one sequence is available representing that group) or presents the user with a pop-up menu of available sequences. Alternatively, the user can choose the desired sequence from a list containing the names of all of the available sequences, or choose to search the sequence names for a specific character string. The ssu rRNA sequence stack is written in Hypertalk v. 2.1, and requires v. 2.0 (or greater) of HyperCard, which in turn requires at least a Macintosh Plus, 1 Mbyte of RAM, the Macintosh operating system v 6.0.5 (or greater), and preferably a hard disk drive. The ssu rRNA sequence stack is available by anonymous FTP from ftp.bio.indiana.edu, by E-mail from the author at jwbrown@bio.indiana.edu or brownjw@iubacs.bitnet, or on floppy disk (enclose a single formatted high-density disk) free of charge on written request to the author.
7956229
How laminar frontal cortex and basal ganglia circuits interact to control planned and reactive saccades
How does the brain learn to balance between reactive and planned behaviors? The basal ganglia (BG) and frontal cortex together allow animals to learn planned behaviors that acquire rewards when prepotent reactive behaviors are insufficient. This paper proposes a new model, called TELOS, to explain how laminar circuitry of the frontal cortex, exemplified by the frontal eye fields, interacts with the BG, thalamus, superior colliculus, and inferotemporal and parietal cortices to learn and perform reactive and planned eye movements. The model is formulated as fourteen computational hypotheses. These specify how strategy priming and action planning (in cortical layers III, Va and VI) are dissociated from movement execution (in layer Vb), how the BG help to choose among and gate competing plans, and how a visual stimulus may serve either as a movement target or as a discriminative cue to move elsewhere. The direct, indirect and hyperdirect pathways through the BG are shown to enable complex gating functions, including deferred execution of selected plans, and switching among alternative sensory-motor mappings. Notably, the model can learn and gate the use of a What-to-Where transformation that enables spatially invariant object representations to selectively excite spatially coded movement plans. Model simulations show how dopaminergic reward and non-reward signals guide monkeys to learn and perform saccadic eye movements in the fixation, single saccade, overlap, gap, and delay (memory-guided) saccade tasks. Model cell activation dynamics quantitatively simulate seventeen established types of dynamics exhibited by corresponding real cells during performance of these tasks.
645538
Plant snoRNA database
The Plant snoRNA database (http://www.scri.sari.ac.uk/plant_snoRNA/) provides information on small nucleolar RNAs from Arabidopsis and eighteen other plant species. Information includes sequences, expression data, methylation and pseudouridylation target modification sites, initial gene organization (polycistronic, single gene and intronic) and the number of gene variants. The Arabidopsis information is divided into box C/D and box H/ACA snoRNAs, and within each of these groups, by target sites in rRNA, snRNA or unknown. Alignments of orthologous genes and gene variants from different plant species are available for many snoRNA genes. Plant snoRNA genes have been given a standard nomenclature, designed wherever possible, to provide a consistent identity with yeast and human orthologues.
10597458
Computational and neural mechanisms of task switching
Switching between tasks that overlap in perceptual and response characteristics is assumed to rely upon the maintenance of task representations in prefrontal cortex (PFC). However, task-switching studies demonstrate ''switch costs,'' even when there is sufficient time to prepare for a new task. These costs suggest that task-switching performance reflects a complex interplay between priming and the updating and maintenance of task representations. We describe a computational model in which this interaction is made explicit and linked to the dynamics of PFC. Simulation results account for a variety of empirical phenomena and predict a double dissociation in lateral PFC that was subsequently identified.