Frontal Lobe Function and Performance Monitoring following Total Sleep Deprivation

Imaging studies have shown reduced frontal lobe resources following total sleep deprivation (TSD). The anterior cingulate cortex (ACC) in the frontal region plays a role in performance monitoring and cognitive control; both error detection and response inhibition are impaired following sleep loss. Event-related potentials (ERPs) are an electrophysiological tool used to index the brain's response to stimuli and information processing. In the Flanker task, the error-related negativity (ERN) and error positivity (Pe) ERPs are elicited after erroneous button presses. In a Go/NoGo task, NoGo-N2 and NoGo-P3 ERPs are elicited during high conflict stimulus processing. Research investigating the impact of sleep loss on ERPs during performance monitoring is equivocal, possibly due to task differences, sample size differences and varying degrees of sleep loss. Based on the effects of sleep loss on frontal function and prior research, it was expected that the sleep deprivation group would have lower accuracy, slower reaction time and impaired remediation on performance monitoring tasks, along with attenuated and delayed stimulus- and response-locked ERPs. In the current study, 49 young adults (24 male) were screened to be healthy good sleepers and then randomly assigned to a sleep deprived (n = 24) or rested control (n = 25) group. Participants slept in the laboratory on a baseline night, followed by a second night of sleep or wake. Flanker and Go/NoGo tasks were administered in a battery at 1O:30am (i.e., 27 hours awake for the sleep deprivation group) to measure performance monitoring. On the Flanker task, the sleep deprivation group was significantly slower than controls (p's <.05), but groups did not differ on accuracy. No group differences were observed in post-error slowing, but a trend was observed for less remedial accuracy in the sleep deprived group compared to controls (p = .09), suggesting impairment in the ability to take remedial action following TSD. Delayed P300s were observed in the sleep deprived group on congruent and incongruent Flanker trials combined (p = .001). On the Go/NoGo task, the hit rate (i.e., Go accuracy) was significantly lower in the sleep deprived group compared to controls (p <.001), but no differences were found on false alarm rates (i.e., NoGo Accuracy). For the sleep deprived group, the Go-P3 was significantly smaller (p = .045) and there was a trend for a smaller NoGo-N2 compared to controls (p = .08). The ERN amplitude was reduced in the TSD group compared to controls in both the Flanker and Go/NoGo tasks. Error rate was significantly correlated with the amplitude of response-locked ERNs in control (r = -.55, p=.005) and sleep deprived groups (r = -.46, p = .021); error rate was also correlated with Pe amplitude in controls (r = .46, p=.022) and a trend was found in the sleep deprived participants (r = .39, p =. 052). An exploratory analysis showed significantly larger Pe mean amplitudes (p = .025) in the sleep deprived group compared to controls for participants who made more than 40+ errors on the Flanker task. Altered stimulus processing as indexed by delayed P3 latency during the Flanker task and smaller amplitude Go-P3s during the Go/NoGo task indicate impairment in stimulus evaluation and / or context updating during frontal lobe tasks. ERN and NoGoN2 reductions in the sleep deprived group confirm impairments in the monitoring system. These data add to a body of evidence showing that the frontal brain region is particularly vulnerable to sleep loss. Understanding the neural basis of these deficits in performance monitoring abilities is particularly important for our increasingly sleep deprived society and for safety and productivity in situations like driving and sustained operations.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

The role of daytime napping in sleepiness and cognitive function in 24-70 year olds /

Daytime napping improves well-being and performance for young adults. The benefits of napping in older adults should be investigated because they have fragmented nocturnal sleep, cognitive declines, and more opportunity to nap. In addition, experience with napping might influence the benefits of napping. Study 1 examined the role of experience with napping in young adults. Habitual (n = 23) and non-habitual nappers (n = 16) were randomly assigned to a 20-minute nap or a 20- minute reading condition. Both groups slept the same according to macro architecture. However, microarchitecture showed greater theta, alpha, and beta power during Stage 1, and greater delta, alpha, and sigma power during Stage 2 for habitual nappers, for the most part indicating better sleep. Both groups felt less sleepy after the nap. P2 latency, reflecting information processing, decreased after the nap for habitual nappers, and after the control condition for non-habitual nappers. In sum, both groups who slept felt better, but only the habitual nappers who napped gained a benefit in terms of information processing. Based on this outcome, experience with napping was investigated in Study 2. Study 2 examined the extent to which daytime napping enhanced cognition in older adults, especially frontal lobe function. Cognitive deficits in older adults may be due to sleep loss and age-related decline in brain functioning. Longer naps were expected to provide greater improvement, particularly for older adults, by reducing sleep pressure. Thirty-two adults, aged 24-70 years, participated in a repeated measures dose-response manipulation of sleep pressure. Twenty- and sixty-minute naps were compared to a no-nap condition in three age groups. Mood, subjective sleepiness, reaction time, working memory, 11 novelty detection, and waking electro physiological measures were taken before and after each condition. EEG was also recorded during each nap or rest condition. Napping reduced subjective sleepiness, improved working memory (serial addition / subtraction task), and improved attention (reduced P2 amplitude). Physiological sleepiness (i.e., waking theta power) increased following the control condition, and decreased after the longer nap. Increased beta power after the short nap, and seen with older adults overall, may have reflected increased mental effort. Older adults had longer latencies and smaller amplitudes for several event-related potential components, and higher beta and gamma power. Following the longer nap, gamma power decreased for older adults, but increased for young adults. Beta and gamma power may represent enhanced alertness or mental effort. In addition, Nl amplitude showed that benefits depend on the preceding nap length as well as age. Since the middle group had smaller Nl amplitudes following the short nap and rest condition, it is possible that they needed a longer nap to maintain alertness. Older adults did not show improvements to Nl amplitude following any condition; they may have needed a nap longer than 60 minutes to gain benefits to attention or early information processing. Sleep characteristics were not related to benefits of napping. Experience with napping was also investigated. Subjective data confirmed habitual nappers were happier to nap, while non-habitual nappers were happier to stay awake, reflecting self-identified napping habits. Non-habitual nappers were sleepier after a nap, and had faster brain activity (i.e., heightened vigilance) at sleep onset. These reasons may explain why non-habitual nappers choose not to nap.

Individual differences in risk-taking and associated characteristics : a test of specificity in executive functions /

Multiple measures have been devised by clinicians and theorists from many different backgrounds for the purpose of assessing the influence of the frontal lobes on behaviour. Some utilize self-report measures to investigate behavioural characteristics such as risktaking, sensation seeking, impulsivity, and sensitivity to reward and punishment in an attempt to understand complex human decision making. Others rely more on neuroimaging and electrophysiological investigation involving experimental tasks thought to demonstrate executive functions in action, while other researchers prefer to study clinical populations with selective damage. Neuropsychological models of frontal lobe functioning have led to a greater appreciation of the dissociations among various aspects of prefrontal cortex function. This thesis involves (1) an examination of various psychometric and experimental indices of executive functions for coherence as one would predict on the basis of highly developed neurophysiological models of prefrontal function, particularly those aspects of executive function that involve predominantly cognitive abilities versus processes characterized by affect regulation; and (2) investigation of the relations between risk-taking, attentional abilties and their associated characteristics using a neurophysiological model of prefrontal functions addressed in (1). Late adolescence is a stage in which the prefrontal cortices undergo intensive structural and functional maturational changes; this period also involves increases in levels of risky and sensation driven behaviours, as well as a hypersensitivity to reward and a reduction in inhibition. Consequently, late adolescence spears to represent an ideal developmental period in which to examine these decision-making behaviours due to the maximum variability of behavioural characteristics of interest. Participants were 45 male undergraduate 18- to 19-year olds, who completed a battery of measures that included self-report, experimental and behavioural measures designed to assess particular aspects of prefrontal and executive functioning. As predicted, factor analysis supported the grouping of executive process by type (either primarily cognitive or affective), conforming to the orbitofrontal versus dorsolateral typology; risk-taking and associated characteristics were associated more with the orbitofrontal than the dorsolateral factor, whereas attentional and planning abilities tended to correlate more strongly with the dorsolateral factor. Results are discussed in light of future assessment, investigation and understanding of complex human decision-making and executive functions. Implications, applications and suggestions for future research are also proposed.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Developmental and individual differences in novelty and error detection in 10-year-old children and young adults /

Event-related potentials were recorded from 10-year-old children and young adults in order to examine the developmental dififerences in two frontal lobe functions: detection of novel stimuli during an auditory novelty oddball task, and error detection during a visual flanker task. All participants showed a parietally-maximal P3 in response to auditory stimuli. In children, novel stimuli generated higher P3 amplitudes at the frontal site compared with target stimuli, whereas target stimuli generated higher P3 amplitudes at the parietal site compared with novel stimuli. Adults, however, had higher P3 amplitude to novel tones compared with target tones at each site. Children also had greater P3 amplitude at more parietal sites than adults during the novelty oddball and flanker tasks. Furthermore, children and adults did not show a significant reduction in P3 amplitude from the first to second novel stimulus presentation. No age differences were found with respect to P3 latency to novel and target stimuli. These findings suggest that the detection of novel and target stimuli is mature in 10-year-olds. Error trials typically elicit a negative ERP deflection (the ERN) with a frontal-central scalp distribution that may reflect response monitoring. There is also evidence of a positive ERP peak (the Pe) with a posterior scalp distribution which may reflect subjective recognition of a response. Both children and adults showed an ERN and Pe maximal at frontal-central sites. Children committed more errors, had smaller ERN across sites, and had a larger Pe at the parietal site than adults. This suggests that response monitoring is still immature in 10-year-olds whereas recognition of and emotional responses to errors may be similar in children and adults.