Search

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit O (n) -bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges. [ABSTRACT FROM AUTHOR]

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins. [ABSTRACT FROM AUTHOR]

• This paper proposes an algorithm for network reliability with imperfect vertices. • The proposed algorithm constructs a binary decision diagram without creating intermediate representation. • The proposed algorithm runs 50–1000 times faster than existing algorithms for some benchmark networks. This paper discusses evaluation of the network reliability with imperfect vertices, which computes the probability that a subset of nodes is communicable under possible failures of links and nodes. Although the network reliability is efficiently computed utilizing a binary decision diagram (BDD) if assuming link failures only, it can be 10 times slower if considering node failures as well. This is because existing algorithms are designed to repeatedly update a BDD for every node failure in a step-by-step manner. This research proposes an algorithm that creates the final BDD without the redundant repetitions, which greatly improves the computation efficiency. Moreover, this paper presents a better variable order of BDDs among variables corresponding to links and nodes. Under the variable order, the proposed algorithm is compared with existing ones by numerical experiments using various benchmark networks including real communication networks. The results show that the proposed algorithm runs 198.2 times faster than the existing ones for the 10-by-10 grid graph, 1074.6 times faster for the complete graph with 12 vertices, and 65.6 times faster for some well-known benchmark network. For some network instances, the proposed variable order reduces the number of BDD nodes by 15–38% compared with the existing order. This paper reveals that considering imperfect vertices does not impose significant performance overheads. [ABSTRACT FROM AUTHOR]

Abstract Visual marking, which is based on the assumption that previewing some distractors increases the efficiency of subsequent visual searches, constitutes one of the most efficient inhibitions on visual searches. The preview search task consists of a display of a subset of distractors followed by an additional display containing the remaining distractors and a target. During the preview period, an inhibitory template is thought to be formed, resulting in the prioritization of the subsequently presented items and the inhibition of the previewed items. Although the previous studies have mainly examined the determinants that impair the inhibitory templates resulting in inefficient visual searches, the present study examined the possibility that the template could be updated to increase search efficiency. To this end, we used a preview search task and manipulated the presence of a singleton distractor in the display of the additional items. We examined whether the singleton increased the efficiency of the search performance by determining if the inhibitory template would be updated such that participants would treat the singleton as if it had been previewed. The results demonstrated that the response times were faster with the singleton included, suggesting that an inhibitory template for visual marking could be updated and lead to improved search performance. Highlights • A color singleton distractor among additional items enhanced search performance when visual marking occurred. • A color singleton distractor did not enhance search performance in the ordinary simultaneous search task. • A color singleton distractor among additional items did not enhance search performance when visual marking did not occur. • Only a color cuing did not enhance search performance in the ordinary simultaneous search task. [ABSTRACT FROM AUTHOR]

We consider a variant of the online buffer management problem in network switches, called the k -frame throughput maximization problem ( k -FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k = 2 . They also introduced an “order-respecting” variant of k -FTM, called k -OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most 2 k B ⌊ B / k ⌋ + k for any B ≥ k , where B is the size of the buffer. They also gave a lower bound of B ⌊ 2 B / k ⌋ for deterministic online algorithms when 2 B ≥ k and k is a power of 2. In this paper, we improve upper and lower bounds on the competitive ratio of k -OFTM. Our main result is to improve an upper bound of O ( k 2 ) by Kesselman et al. to 5 B + ⌊ B / k ⌋ − 4 ⌊ B / 2 k ⌋ = O ( k ) for B ≥ 2 k . Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Ω ( k ) . We also give two lower bounds. First we give a lower bound of 2 B ⌊ B / ( k − 1 ) ⌋ + 1 on the competitive ratio of deterministic online algorithms for any k ≥ 2 and any B ≥ k − 1 , which improves the previous lower bound of B ⌊ 2 B / k ⌋ by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of k − 1 against an oblivious adversary for any k ≥ 3 and any B . Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10 k , this indicates that randomization does not help too much. [ABSTRACT FROM AUTHOR]

The automatic evacuation guiding using mobile devices is a promising disaster-response approach for large-scale disasters. When a disaster occurs, each mobile device recommends a route to a refuge and automatically estimates the state of road segments by comparing the recommended route and observed trajectory. The estimated information is shared among devices using available communication technologies. This scheme assumes that each evacuee follows the recommended route but it might not be satisfied when an evacuee behaves as an outlier taking unexpected movement, which will disturb the normal evacuation. This paper analyzes the effects of outliers and reveals the following characteristics through simulations: The number of passable road segments misestimated as impassable increases with outliers; Many of them, however, can be corrected by passable estimation from other outliers; The remaining misestimation increases the evacuation completion time of 26.5% of normal evacuees by more than 100 s. Since the speedy and accurate outlier detection is difficult in the severe communication environments, this paper alternatively proposes a mechanism that delays to judge a road segment as impassable until gathering the corresponding impassable estimation from M devices. The simulation results show that M = 2 achieves a balance between the speediness and safety in evacuation guiding. [ABSTRACT FROM AUTHOR]

The present study examined whether attention can be flexibly controlled to monitor two different feature dimensions (shape and color) in a temporal search task. Specifically, we investigated the occurrence of contingent attentional capture (i.e., interference from task-relevant distractors) and resulting set reconfiguration (i.e., enhancement of single task-relevant set). If observers can restrict searches to a specific value for each relevant feature dimension independently, the capture and reconfiguration effect should only occur when the single relevant distractor in each dimension appears. Participants identified a target letter surrounded by a non-green square or a non-square green frame. The results revealed contingent attentional capture, as target identification accuracy was lower when the distractor contained a target-defining feature than when it contained a nontarget feature. Resulting set reconfiguration was also obtained in that accuracy was superior when the current target's feature (e.g., shape) corresponded to the defining feature of the present distractor (shape) than when the current target's feature did not match the distractor's feature (color). This enhancement was not due to perceptual priming. The present study demonstrated that the principles of contingent attentional capture and resulting set reconfiguration held even when multiple target feature dimensions were monitored. [ABSTRACT FROM AUTHOR]

Highlights: [•] Low-voltage passive-matrix electrochromic displays manufactured by printing tools. [•] A threshold voltage is obtained in a simple three-layer pixel architecture. [•] The threshold voltage enables unique pixel addressability in the resulting display. [•] The electrolyte is deposited by using a novel surface energy patterning method. [•] The results promise for true low-cost manufacturing of flexible displays. [Copyright &y& Elsevier]

Highlights: [•] Nanofibrillated cellulose is hybridized with PEDOT:PSS or polyelectrolyte. [•] The resulting membranes are self-supporting and self-adhesive. [•] Displays and transistors are obtained upon lamination of the hybrid membranes. [•] System integration of electronic components is simplified. [•] A novel concept of system reconfiguration is also proven. [ABSTRACT FROM AUTHOR]

Abstract: Poly(3,4-ethylenedioxythiophene) chemically doped with poly(styrene sulfonic acid) (PEDOT:PSS) is a material system commonly used as a conductive and transparent coating in several important electronic applications. The material is also electrochemically active and exhibits electrochromic (EC) properties making it suitable as the active element in EC display applications. In this work uniformly coated PEDOT:PSS layers were used both as the pixel electrode and as the counter electrode in EC display components. The pixel and counter electrodes were separated by a whitish opaque and water-based polyelectrolyte and the thicknesses of the two EC layers were varied independently in order to optimize the color contrast of the display element. A color contrast (ΔE ∗, CIE L ∗ a ∗ b ∗ color space) exceeding 40 was obtained with maintained relatively short switching time at an operational voltage less than 2V. [Copyright &y& Elsevier]

Abstract: The presence of a singleton in a task-irrelevant domain can impair visual search. This impairment, known as the attentional capture depends on the set of participants. When narrowly searching for a specific feature (the feature search mode), only matching stimuli capture attention. When searching broadly (the singleton detection mode), any oddball captures attention. The present study examined which strategy represents the “default” mode using an operant conditioning approach in which participants were trained, in the absence of explicit instructions, to search for a target in an ambiguous context in which one of two modes was available. The results revealed that participants behaviorally adopted the singleton detection as the default mode but reported using the feature search mode. Conscious strategies did not eliminate capture. These results challenge the view that a conscious set always modulates capture, suggesting that the visual system tends to rely on stimulus salience to deploy attention. [Copyright &y& Elsevier]

We consider the one-dimensional version of the online unit clustering problem, proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: “Points” are given online on the line one by one. An algorithm creates a “cluster,” which is a line segment. The initial length of a cluster is 0, and an algorithm can extend a cluster until it reaches unit length. The task of an algorithm is to cover a new given point either by creating a new cluster and assigning the point to the cluster or by extending an existing cluster created in past times. The goal is to minimize the total number of created clusters. In this paper, we show a lower bound of 13 / 8 = 1.625 on the competitive ratio of any deterministic online algorithm for the one-dimensional unit clustering, improving the previous lower bound 8 / 5 ( = 1.6 ) presented by Epstein and van Stee (WAOA2007 and ACM Transactions on Algorithms 7(1), 2010). Note that Ehmsen and Larsen (SWAT2010 and Theoretical Computer Science, 500, 2013) showed the current best upper bound of 5/3. [ABSTRACT FROM AUTHOR]

The allocation of attention is affected by internal emotional states, such as anxiety and depression. The attention captured by real images of negative faces can be quantified by emotional probe tasks. The present study investigated whether attentional bias toward drawings of negative faces (line drawings and cartoon faces) differs from that of real faces. Non-clinical university students indicated their levels of anxiety and depression via self-report questionnaires, and completed a probe discrimination task under three face image conditions in a between-participants design. Significant correlations were found between bias scores and scores on the self-reported BDI-II under the real face condition. However, two types of face drawings were only weakly correlated with self-report scores. In our probe task to investigate attentional bias to facial stimuli in nonclinical adults, the strength of the relationship between depression and attentional bias to negative face was stronger for real faces than for face drawings. • We tested whether attentional bias to negative face drawings (line drawings and cartoons) differed from that of real faces. • Participants who rated themselves as highly depressed showed attentional bias toward negative real faces. • There was no attentional bias toward or away from line drawings or cartoons of negative faces. • We suggested that real faces are more sensitive than drawings for testing attentional bias. [ABSTRACT FROM AUTHOR]

Abstract: Symmetric and fast (∼5ms) on-to-off and off-to-on drain current switching characteristics have been obtained in screen printed organic electrochemical transistors (OECTs) including PEDOT:PSS (poly(3,4-ethylenedioxythiophene) doped with poly(styrene sulfonic acid)) as the active transistor channel material. Improvement of the drain current switching characteristics is made possible by including a carbon conductor layer on top of PEDOT:PSS at the drain electrode that is in direct contact with both the channel and the electrolyte of the OECT. This carbon conductor layer suppresses the effects from a reduction front that is generated in these PEDOT:PSS-based OECTs. In the off-state of these devices this reduction front slowly migrate laterally into the PEDOT:PSS drain electrode, which make off-to-on switching slow. The OECT including carbon electrodes was manufactured using only standard printing process steps and may pave the way for fully integrated organic electronic systems that operate at low voltages for applications such as logic circuits, sensors and active matrix addressed displays. [Copyright &y& Elsevier]

Abstract: It has been a long-standing open problem to determine the exact randomized competitiveness of the -server problem, that is, the minimum competitiveness of any randomized online algorithm for the -server problem. For deterministic algorithms the best competitive ratio that can be obtained is and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. (1998)  give a competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the -server problem over Cross Polytope Spaces . We obtain an algorithm with competitive ratio of , and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than-competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to . [ABSTRACT FROM AUTHOR]

Abstract: In an inefficient visual search task, when some distractors (old items) temporally precede some others (new items), the old items are excluded from the search, a phenomenon termed visual marking. This effect is said to occur because the locations of the old items are inhibited before the new items appear. The present study used a probe-detection task to examine whether this inhibition occurs only at the precise locations of old items or at and around the locations of old items. We also investigated the effect of inhibition overreaching boundaries to encompass neighboring regions. Participants searched for a target or detected a probe that appeared after the new items appeared. The results revealed that the probe reaction times at locations inside grouped regions were longer than those at a blank region where no items had been presented and were comparable to those at a location occupied by old items. Probe detection was not delayed when the probe was presented near but external to the external boundary of the grouped regions. The overreaching effect was obtained before and after the new items appeared. We conclude that the inhibitory template for visual marking represents clusters of old items for at least 200ms before the onset of new items, and that this spatial schema is preserved until at least 200ms after the onset of new items. [Copyright &y& Elsevier]

Consider a puzzle consisting of n tokens on an n -vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 α -approximation algorithm for graphs whose tree α -spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Primary cognitive processes, such as spatial attention, are essential to our higher cognitive abilities and develop dramatically in the first year of life. The spatial aspect of infants' working memory is equivalent to that of adults. However, it is unclear whether this is true for the temporal domain. Thus, we investigated the temporal aspect of infants' working memory using an attentionally demanding task by focusing on the attentional blink effect, in which the identification of the second of the two brief targets is impaired when inter-target lags are short. We argue that finding a similar pattern of the attentional blink in preverbal infants and adults indicates that infants can complete the consolidation of the first target into working memory at a similar temporal scale as adults. In this experiment, we presented 7- to 8-month-old infants with rapid serial visual streams at a rate of 100 ms/item, including two female faces as targets, and examined whether they could identify the targets by measuring their preference to novel faces compared to targets. The temporal separation between the two targets was 200 or 800 ms. We found that the infants could identify both targets under the longer lag, but they failed to identify the second target under the shorter lag. The adult experiment using the same temporal separation as in the infant experiment revealed the attentional blink effect. These results suggest that 7- to 8-month-old infants can consolidate two items into working memory by 800 ms but not by 200 ms. [ABSTRACT FROM AUTHOR]