Determining the chromatic number of a graph is known to be NP-hard. We will consider the problem of coloring a $k$-colorable graph on n vertices with $n^{\alpha}$ colors (where $\alpha < 1$).
Considering the large volume of sequence data that many computational biology applications must deal with, proper organization of the data to facilitate fast access is important to achieve desirable run-times.
<p>Pinaki Mazumder<br />
University of Michigan<br />
Department of Electrical Engineering<br />
and Computer Science<br />
2260 Howard Avenue<br />
Ann Arbor, MI 48109-2121<br />
United States of America</p>
Conventional shrinking methods to improve VLSI chip performance by continual scaling of device and interconnect geometries may allow CMOS juggernaut to reach about 22 nm nodes.
Our input is a graph $G = (V, E)$ where each vertex ranks its neighbors in a strict order of preference. The problem is to compute a matching in $G$ that captures the preferences of the vertices in a popular way.
The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large.
Diverse engineering functions can be generated when simple modules are connected in different configurations. Similar modules also exist in biology, for example, within circuits of interacting molecules that map to diverse cellular behavior.
Insurance transfers losses associated with risks to the insurer for a price, the premium. We adopt the collective risk approach. Namely, we abstract the problem to include just two agents: the insured and the insurer.
We explore the visibility graph of a point set. We list some classical works on configurations of points and straight lines on the plain and then proceed to deduce some combinatorial properties of point visibility graphs.
