51 |
The Coloring and Routing Problems on de Bruijn Interconnection NetworksMao, Jyh-Wen 01 September 2003 (has links)
de Bruijn graphs are attractive due to its simplicity of routing messages between two nodes and the capability of fault tolerance. The shortest path from a node V to a node W in the directed binary de Bruijn graph can be obtained by firstly determining the longest substring, common to the right/left of V and to the left/right of W. Then L-operations/R-operations are performed to finish this routing process. However, this method does not always find the shortest path in the undirected binary de Bruijn graph. In this dissertation, we propose a shortest path routing algorithm which requires O(m2) time. We also design a fault-tolerant routing algorithm which provides the shortest path and another node-disjoint path of length at most m + log2m + 4. Our algorithm can tolerate one node failure in the m-dimensional binary de Bruijn network.
In concurrent systems, a 1-fair alternator design is optimal if each processor can execute the critical step once in the fewest steps. This problem corresponds to use the minimum number of colors to color the processors in the system. Thus, the optimal
design of a 1-fair alternator problem can be transformed into the coloring problem. We propose a simple and fast algorithm to solve the node coloring problem on the undirected binary de Bruijn graph. In our algorithm, the number of colors used is 3, and it is an optimal design. We also extend our method to solve the coloring problem on k-ary de Bruijn graphs. We first present a simple algorithm which needs 2k colors. By slight improvement, the number of required colors is reduced to k+1.
|
52 |
1-Fair Alternator Designs for the de Bruijn NetworkLin, Hsu-Shen 01 September 2006 (has links)
An alternator is a self-stabilizing system which consists of a network of concurrent processors. One of its properties is that any two processors of an alternator system cannot execute the critical step at the same time if
they are adjacent. This exclusion property transforms the alternator design problem into the coloring problem.
And an alternator is said to be 1-fair if no processor executes the critical step twice when one or more other processors have not executed the critical step yet. The simplicity of routing message and the capability of fault
tolerance of de Bruijn networks attract us to design 1-fair alternator on them.
In this thesis, two algorithms are proposed to solve the coloring problem on the de Bruijn network. The first one uses $2ceil{log_2k}+1$ colors to color the $k$-ary de Bruijn graph with two digits, while the second one uses $p+1$ only colors, where ${{p-1}choose{floor{(p-1)/2}}} < k leq {pchoose{floor{p/2}}}$. We also prove that the second coloring method is optimal when $k = {pchoose{floor{p/2}}}$. In other words, the chromatic number of the
$k$-ary de Bruijn graph with two digits is $p+1$, where
$k = {pchoose{floor{p/2}}}$. Furthermore, the extension of our coloring method can be applied to the $k$-ary de Bruijn graph with three or more digits.
|
53 |
An Improved Algorithm for the Nearly Equitable Edge-Coloring ProblemHIRATA, Tomio, NAKANO, Shin-ichi, ONO, Takao, XIE, Xuzhen 01 May 2004 (has links)
No description available.
|
54 |
Homomorphisms of (j, k)-mixed graphsDuffy, Christopher 28 August 2015 (has links)
A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs).
A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively.
In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number.
In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of
iii
a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs.
In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs.
In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. / Graduate
|
55 |
A study of introduced clones of sweet orange (Citrus sinensis) and postharvest degreening of 'Valencia late' oranges in Kenya /Kiuru, Paul D. N. (David Ngugi) January 1994 (has links)
The performance of eleven 'Valencia Late' and nine 'Washington Navel' orange (Citrus sinensis) clones all on rough lemon (Citrus jambhiri) rootstock was evaluated. Significant differences in trunk cross sectional area, plant canopy volume, cumulative yield and yield efficiency were found between clones of different citrus cultivars. Some clones such as VL106, VL139, VL185 and WN204 appeared to be promising in terms of good growth characteristics and high yield, and could therefore be used for the national performance trials. Studies on post-harvest degreening of 'Valencia Late' oranges were also carried out at Matuga Regional Research Sub-Centre (Kenya) in a series of experiments. Fully mature fruits were dipped for three minutes in 0, 500, 1000, 1500, 2000, 2500 and 3000 ppm concentrations of ethephon. Fruits wrapped in aluminum foil shrivelled less and retained their firmness and freshness. Rind brightness increased by dipping of fruits in ethephon (2000) ppm giving a good colour change. Dipping fruits a second time three days after the first dip did not have any significant effect on colour change. (Chemical names used: (2-Chloroethyl)phosphonic acid (ethephon).
|
56 |
Graph coloring in sparse derivative matrix computationGoyal, Mini, University of Lethbridge. Faculty of Arts and Science January 2005 (has links)
There has been extensive research activities in the last couple of years to efficiently determine large sparse Jacobian matrices. It is now well known that the estimation of Jacobian matrices can be posed as a graph coloring problem. Unidirectional coloring by Coleman and More [9] and bidirectional coloring independently proposed by Hossain and Steihaug [23] and Coleman and Verma [12] are techniques that employ graph theoretic ideas. In this thesis we present heuristic and exact bidirectional coloring techniques. For bidirectional heuristic techniques we have implemented variants of largest first ordering, smallest last ordering, and incidence degree ordering schemes followed by the sequential algorithm to determine the Jacobian matrices. A "good" lower bound given by the maximum number of nonzero entries in any row of the Jacobian matrix is readily obtained in an unidirectional determination. However, in a bidirectional determination no such "good" lower bound is known. A significant goal of this thesis is to ascertain the effectiveness of the existing heuristic techniques in terms of the number of matrix-vector products required to determine the Jacobian matrix. For exact bidirectional techniques we have proposed an integer linear program to solve the bidirectional coloring problem. Part of exact bidirectional coloring results were presented at the "Second International Workshop on Cominatorial Scientific Computing (CSC05), Toulouse, France." / viii, 83 leaves ; 29 cm.
|
57 |
Reed's Conjecture and Cycle-Power GraphsSerrato, Alexa 01 January 2014 (has links)
Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.
|
58 |
Radish anthocyanin extract as a natural red colorant for maraschino cherriesHundskopf, Maria Monica Giusti 07 April 1995 (has links)
Red radish anthocyanin extract (RAE) was investigated for coloring brined
cherries as an alternative to FD&C Red No. 40. Red radish (Raphanus sativus L.)
anthocyanins were extracted from liquid nitrogen powdered epidermal tissue using
acetone, partitioned with chloroform, and isolated using C-18 resin. The monomeric
anthocyanin content was determined by pH differential to be 154 ± 13 mg/100 g of
epidermal tissue (on pelargonidin-glucoside basis). The major pigments were
identified as pelargonidin-3-sophoroside-5-glucoside monoacylated with p-coumaric
or ferulic acids by HPLC and spectral analyses. Primary and secondary bleached
cherries were sweetened to 40° Brix (pH of 3.50), and colored using two
concentrations of RAE (600 and 1200 mg/L syrup, designated Cl and C2) and
FD&C Red No. 40 (200 ppm). Color was measured for both cherries and syrup.
Reflectance measurements (CIE L*, a*, b*), chroma and hue angle, showed that
RAE imparted red color to the cherries and syrup extremely close to that of FD&C
Red No. 40. RAE C2 gave the primary bleached cherries the closest color
characteristics (L*= 18.20, a*= 20.00, b*= 8.47) to FD&C Red No. 40 (L*= 18.00, a*= 24.35, b*= 12.13). RAE Cl gave the secondary bleached cherries the closest color
characteristics (L*= 15.27, a*= 16.21, b*= 5.21) to FD&C Red No. 40 (L*= 16.38,
a*= 19.91, b*= 8.99). Color and pigment stability of secondary bleached cherries
were evaluated during a year of storage in the dark at 25°C. Monomeric anthocyanin
degradation followed first-order kinetics and the half-lives were 29 and 33 weeks for
syrups colored with RAE Cl and RAE C2, respectively. However, cherry color
showed no significant changes in hue, color intensity nor lightness during storage.
Color changes of syrup samples over time were dependant on anthocyanin
concentration, higher anthocyanin concentration exerted a protective effect on color
stability. Haze formation was observed in syrup samples colored with RAE, possibly
due to pigment polymerization.
Syrup samples colored with RAE and FD&C Red No. 40 were also exposed
to light for a year at 25°C. Light had a small but significant effect on L*, a*, and
monomeric anthocyanin content.
From color and pigment stability data and visual observations we concluded
that RAE was effective in coloring secondary bleached cherries with results very
similar to those of FD&C Red No. 40 for 6 months of storage. / Graduation date: 1995
|
59 |
Some factors affecting the stability of erythrosine dye in cherry tissueVan Blaricom, Lester Oscar 06 1900 (has links)
Graduation date: 1940
|
60 |
Diffusion rate of dye in preparation of maraschino cherriesHenney, Edward Nathan 01 May 1951 (has links)
Graduation date: 1951
|
Page generated in 0.0811 seconds