Search

With the demand for data processing and storage increasing rapidly, the existing CMOS-based computing system is gradually unable to meet the amplification demand because of its high-power consumption. Due to high frequency and low power consumption, superconducting rapid single-flux-quantum (RSFQ) logic circuit technology is an attractive candidate. In this paper, we propose a novel placement method based on the layer layout. We layer the gates according to the logic level, which is the length of the longest path in terms of the number of clocked gates from any primary input (PI) of the circuit to the gate. Dummy gates are inserted so that any two adjacent layers can form a bipartite graph. Then the gates of each layer are reordered to minimize the half-perimeter wirelength (HPWL). Finally, the gates of each layer are assigned vertical positions to make the edges as straight as possible. The distance between adjacent layers is determined by the number of bending points of the edges between layers. We use several superconducting RSFQ logic circuits to evaluate the effectiveness of our proposed placement method, which uses HPWL and area as evaluation metrics. The experimental results show that compared with the Simulated Annealing (SA)-based placement method, the proposed approach can reduce the total HPWL and total area by an average of 77.77% and 57.56%, respectively.

This paper firstly proposes a greedy online packet scheduling algorithm for the problem raised by Mao, Koksal and Shroff that allows arbitrary hard deadlines in multi-hop networks aiming at maximizing the total revenue. With the same assumption of $\rho _{M} / \rho _{m}={O}(1)$ where $\rho _{M}$ and $\rho _{\textit {}m}$ are the maximum and minimum revenue a packet may carry, our algorithm is ${O}$ ( ${P} _{M}$ )-competitive improving on MKS algorithm by a factor of ${O}$ (log ${P} _{M}$ ), where ${P} _{M}$ is the length of the longest path a packet may travel in the network. We prove that it is asymptotically optimal by presenting a lower bound of ${P} _{M}$ on the competitiveness for this problem. Secondly, this paper studies the extension of this problem that includes routing as a part of the solution. We prove that using the fastest path algorithm for the routing part, the greedy online algorithm also achieves asymptotically optimal competitiveness for the extended problem. Furthermore, we present a non-greedy online algorithm that not only is asymptotically optimal, but also can adaptively achieve a better competitiveness when the network has a larger ${C} _{\textit {min}}$ , where ${C} _{\textit {min}}$ is the minimum link capacity in the network. Finally, simulation results are reported, showing that not only do the greedy online algorithms achieve asymptotically optimal bounds, but also practically achieve better performance than the previously proposed algorithms.

When each task of the longest path in a task-dependent scientific workflow must meet a deadline, the path is called critical. Tasks in a critical path have priority over tasks in non-critical paths. Considering this fact that less methods have already dealt with the critical path problem for workflow scheduling in cloud, this study aims to present a critical-path based method to consider the problem based on our previous optimal workflow scheduling method, GWO-based (Grey Wolf Optimization). We applied our study to balance and imbalance scientific workflows. Our results show that considering the critical path improves the completion time of workflows while maintaining a proper level of resource cost and resource utilization. Moreover, to show the effectiveness of the current study, we compared the performance of the proposed method with non-critical-path aware algorithms, using three different indicators. The simulation demonstrates that compared to PGWO as the base method, the proposed approach achieves (1) approximately 68% improvement for makespan, (2) more accuracy in population sampling for about 70% of workflows, and (3) avoidance of the cost increases in more than 50% of workflows. Moreover, the proposed method decreases makespan approximately 3 times compared to the constrained-based approaches.

In large and complex project schedule networks, existing algorithms to determine the critical path are considerably slow. Therefore, an algorithm with a faster convergence is needed to improve the efficiency of the critical path computation. The ant colony algorithm was first applied to the travelling salesman problem to determine the shortest path. However, many problems require the longest path in practice; the critical path in the scheduling problem is the longest path in the scheduling network. In this study, an improved ant colony algorithm to determine the critical path by setting the path distance and time as negative, while the transition probability remains unchanged, is proposed. The case of a coal power plant engineering, procurement, and construction (EPC) project was considered. The results show that a peak number of optimal solutions appeared at approximately the 9th iteration; however, instabilities and continued fluctuations were observed even afterward, indicating that the algorithm has a certain randomness. Convergence is apparent at the 29th iteration; after the 34th iteration, a singular optimal solution, the longest or critical path, is obtained, indicating that the convergence rate can be controlled and that the critical path can be obtained by setting appropriate parameters in the solution method. This has been found to improve the efficiency of calculating the critical path. Case validation and algorithm performance testing confirmed that the improved ant colony algorithm can determine the critical path problem and make it computationally intelligent.

Embedding an interconnection network into another network is one of the important problems in parallel processing. In this paper, we study embedding of linear arrays (paths) of maximum length in O-shaped meshes (O-shaped grid graphs). This is equal to finding a longest path in an O-shaped mesh (grid graph). An O-shaped mesh is a 2D mesh that a smaller 2D mesh is removed from it. The removed nodes can be considered as faulty processor. We give a linear-time parallel algorithm for this problem. To show the algorithm finds an optimal path, first we prove some upper bounds on the length of the longest paths, then we show that how our algorithm meets these upper bounds.

Graf problemi su jedni od najvažnijih i najizazovnijih problema u računarskoj znanosti. Razlog tome je što mogu modelirati svijet oko nas na jednostavan i strukturiran način, te se primjenjuju u mnogim stvarnim situacijama. Ovaj rad se fokusira na problem najdužeg puta u netežinskim cikličkim grafovima. Predložena su dva različita pristupa, evolucijski algoritam i algoritam zamjene puteva. Pokazuje se da algoritam zamjene puteva dominira nad evolucijskim algoritmom, kako u smislu vremena izvršavanja, tako i u kvaliteti izlaznih rješenja. Algoritam proizvodi rješenja koja se razlikuju za samo $1\%$ od najbolje-do-sada-izračunatih rješenja u samo nekoliko minuta. Glavna ideja algoritma je iterativno nadograđivati put pronalaženjem novih puteva između čvorova u trenutnom putu. Algoritmi su testirani na skupu podataka Kalodont koji se sastoji od $159,836$ riječi. Graf stvoren nad tim podacima sadrži $159,836$ vrhova i $120,053,427$ rubova. Najbolje-do-sada-izračunato rješenje sastoji se od $26,552$ riječi, a naš je algoritam uspio pronaći rješenje koje se sastoji od $26,521$ riječi. Graph problems are one of the most important, and most challenging problems in Computer Science. This is because they can model the world around us in a simple and structured way and are applied in many real life situations. This thesis focuses on the Longest Path Problem in Unweighted Cyclic Graphs. Two different approaches are proposed, Evolutionary algorithm and Switch Path algorithm. The Switch Path algorithm shows to dominate the Evolutionary algorithm, both in the terms of execution time, and in the quality of output solutions. It produces solutions that differ in only $1\%$ from the best-so-far-computed solution in just a few minutes. The main idea of the algorithm is to iteratively build upon a path by finding new paths between nodes in the current path. The algorithms are tested on the Kalodont dataset which consists of $159,836$ words. This creates a graph with $159,836$ vertices and $120,053,427$ edges. The best-so-far-computed solution consists of $26,552$ words, and our algorithm managed to find a solution consisting of $26,521$ words.

The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution in the general case. This study develops two quadratic unconstrained binary optimization (QUBO) formulations of this well-known problem. The first formulation is based on an approach outlined by (Bauckhage et al., 2018) for the shortest path problem and follows simply from the principle of assigning positions on the path to vertices; using k | V | binary variables, this formulation will find the longest path that visits exactly k of a graph's | V | vertices, if such a path exists. As a point of theoretical interest, we present a second formulation based on degree constraints that is more complicated, but reduces the dependence of the number of variables on k to logarithmic; specifically, it requires | V | + 2 | E | ⌊ log 2 ⁡ k ⌋ + 3 | E | binary variables to encode the longest path problem. We adapt these basic formulations for several variants of the standard longest path problem. Scaling factors for penalty terms and preprocessing time required to construct the Q matrix representing the problem are made explicit in the paper.

Seymour’s Second Neighborhood Conjecture states that every simple oriented graph has a vertex such that the cardinality of its second neighborhood is greater than or equal to the cardinality of its first neighborhood. The conjecture has been shown to hold for various families of digraphs but remains unsettled. A digraph is said to be k -antitransitive if any u to v path of length k implies there is no u to v edge. If the conjecture is shown to hold for k -antitransitive digraphs for an arbitrary k , this would settle it for finite digraphs, as every finite digraph is k -antitransitive for k greater than the length of its longest path. So far, the conjecture has been shown to hold for k -antitransitive simple oriented graphs for k ≤ 5 . In this paper we prove the conjecture for 6-antitransitive simple oriented graphs.

This article studies the task assignment problem for a fleet of dispersed vehicles to efficiently visit a set of target locations where some target locations might be unreachable for one or several vehicles. The objectives are to visit as many target locations as possible by using the minimum number of vehicles while minimizing the vehicles’ total travel time. We first propose a target merging strategy to deal with the optimization problem, which is in general NP-hard, and show that for the special case of a single vehicle, it requires linear time to calculate the maximum number of targets to be visited. Second, we design a longest path-based algorithm and analyze the cases in which the objective to visit the maximum number of targets by using the minimum number of vehicles can be obtained through the proposed algorithm within linear running time. Once the targets to be visited and the corresponding employed vehicles are determined, the marginal-cost-based target inserting principle to be discussed guarantees that the chosen targets will be visited within a computable finite maximal travel time, which is at most twice of the optimal when the cost matrix is symmetric. Integrating the longest path-based algorithm with two target inserting principles used to minimize the vehicles’ total travel time, we design two two-phase task assignment algorithms. Furthermore, we propose a one-phase algorithm to optimize the multiple objectives simultaneously by improving a co-evolutionary multipopulation genetic algorithm. Numerical simulations show that the proposed task assignment algorithms can lead to satisfying solutions against popular genetic algorithms.

The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) [19] . Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O ( n 8 ) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k-thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k-thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs.

Capacity augmentation bound (CAB) is a widely used quantitative metric in theoretical analysis for directed acyclic graph (DAG) parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task’s longest path length to task’s deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold has good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides a more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.

Open pit mine production scheduling assigns mining blocks in different production periods for maximising profits after satisfying geotechnical and operational constraints. In this paper, two Open pit mine production scheduling models were applied in an African copper deposit. The first model is a traditional model with more tight resource constraints; the second model is a more robust model where resource constraints are relaxed by penalizing the objective function. Both the models were solved using two step algorithms: (a) year wise production scheduling using a sequential branch-and-cut algorithm; and (b) an iterative longest path algorithm to improve the solution generated from branch-and-cut. Results demonstrated that due to the tight constraints in Model 1, the optimizer was unable to generate a feasible solution after the first period, therefore the lower limit metal production constraint was eliminated to generate a feasible solution; however, Model 2 was able to generate a feasible solution for all periods. Results show that both the models generated nearly the same amount of ore, waste, metal content, and mine life. Model 2 generates relatively more net present value as compared to Model 1, whereas, the computational time required for solving the scheduling problem is relatively less for Model 1 than for Model 2.

In this paper, a generalized path optimization problem for a weighted digraph (i.e., directed graph) over an additively idempotent semiring was considered. First, the conditions for power convergence of a matrix over an additively idempotent semiring were investigated. Then we proved that the path optimization problem is associated with powers of the adjacency matrix of the weighted digraph. The classical matrix power method for the shortest path problem on the min-plus algebra was generalized to the generalized path optimization problem. The proposed generalized path optimization model encompasses different path optimization problems, including the longest path problem, the shortest path problem, the maximum reliability path problem, and the maximum capacity path problem. Finally, for the four special cases, we illustrate the pictorial representations of the graphs with example data and the proposed method.

This paper considers a joint order acceptance and scheduling problem under a general scenario. A manufacturer receives multiple orders with a given revenue, processing time, release date, due date, deadline, and earliness and tardiness penalties. The manufacturer can be seen as a single-machine system. Due to limited capacity, the manufacturer cannot process every order and needs to determine the optimal set of accepted orders and corresponding production schedule such that the total profit is maximized. The manufacturer can extend its capacity with overtime by paying an additional cost. A time-indexed formulation is presented to model the problem. Two exact algorithms are proposed. The first algorithm, denoted by DPIA-GR, is a dynamic programming (DP)-based algorithm that starts by solving a relaxed version of the original model and successively recovers the relaxed constraint until an optimal solution to the original problem is achieved. The second algorithm, denoted by DPIA-LRGR, improves DPIA-GR by incorporating Lagrangian relaxation (LR). The subgradient method is employed to find the optimal Lagrangian multipliers. The relaxed model in DPIA-GR and the LR model in DPIA-LRGR can be represented using a weighted di-graph. Both algorithms are equivalent to finding the longest path in the graph and applying a graph reduction strategy to prevent unnecessary computational time and memory usage. A genetic algorithm (GA) is also proposed to solve large-scale versions of the problem. Numerical experiments show that both DPIA-GR and DPIA-LRGR solve the problem efficiently and outperform CPLEX and GA, but DPIA-LRGR offers better performance.

The problem of the intersection of longest paths consists in determining the size of a smallest subset of vertices of a graph such that every longest path contains at least one vertex of the set. Given a graph G , we denote the size of this subset by lpt ( G ) . In this work, we show a number of results that enable us to conclude that lpt ( G ) = 1 if G is a chain graph, a P 4 -sparse graph, a starlike graph, a ( P 5 , K 1 , 3 ) -free graph, a graph that is the join of two other graphs or a graph whose blocks are split graphs, interval graphs or graphs with a universal vertex. We also provide upper bounds on lpt ( G ) for ( P 5 , cricket ) -free graphs and graphs that are intersection graphs of subtrees of a spider graph.

Let G = (V, E) be a graph. When a graph is used to model the linkage structure of communication networks, the diameter of a graph gives the length of longest path among all the shortest paths betwe...

In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend ( B 1 ) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open.

Motivation Searching the Longest Common Subsequences of many sequences is called a Multiple Longest Common Subsequence (MLCS) problem which is a very fundamental and challenging problem in many fields of data mining. The existing algorithms cannot be applicable to problems with long and large-scale sequences due to their huge time and space consumption. To efficiently handle large-scale MLCS problems, a Path Recorder Directed Acyclic Graph (PRDAG) model and a novel Path Recorder Algorithm (PRA) are proposed. Results In PRDAG, we transform the MLCS problem into searching the longest path from the Directed Acyclic Graph (DAG), where each longest path in DAG corresponds to an MLCS. To tackle the problem efficiently, we eliminate all redundant and repeated nodes during the construction of DAG, and for each node, we only maintain the longest paths from the source node to it but ignore all non-longest paths. As a result, the size of the DAG becomes very small, and the memory space and search time will be greatly saved. Empirical experiments have been performed on a standard benchmark set of both DNA sequences and protein sequences. The experimental results demonstrate that our model and algorithm outperform the related leading algorithms, especially for large-scale MLCS problems. Availability and implementation This program code is written by the first author and can be available at https://www.ncbi.nlm.nih.gov/nuccore and https://blog.csdn.net/wswguilin. Supplementary information Supplementary data are available at Bioinformatics online.

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity , the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

Network comparison is an essential issue in the analysis of biological, social, and communication networks, and recent network comparisons have required the simultaneous mining of several networks on a similar vertex set. In this work, we study the case where the input consists of a directed acyclic graph D and an undirected graph G on the same vertex set. The goal is then to find the longest path P in D whose vertices induce a connected subgraph of G . This problem is known to be NP -hard and has immediate applications in the analysis of biological networks and foreseeable applications in the analysis of social, information, and communication networks. We propose hereinafter improvements to an existing branch-and-bound method and different resolution approaches based on Integer Linear Programming. We also experimentally evaluate both simulated and real data.

Let l be the length of a longest path in a 2-connected graph G and c the circumference - the length of a longest cycle in G. In 1952, Dirac proved that c , by noting that "actually c , but the proof of this result, which is best possible, is rather complicated". Let L1;L2; :::;Lm be a vine on a longest path of G. In this paper, using the parameter m, we present a more general sharp bound for the circumference c including the bound c as an immediate corollary, based on elementary arguments.

Programmable network devices are on the rise with many applications ranging from improved network management to accelerating and offloading parts of distributed systems. Processor-based SmartNICs, match-action-based switches, and FPGA devices offer on-path programmability. Whereas processor-based SmartNICs are much easier and more versatile to program, they have the huge disadvantage that the resulting throughput may vary strongly and is not easily predictable even to the programmer. We want to close this gap by presenting a methodology which, given a SmartNIC program, determines the achievable throughput of this SmartNIC program in terms of achievable packet rate and bit rate. Our approach combines incremental longest path search with SMT checks to establish a lower bound for the slowest satisfiable program path. By analyzing only the slowest program paths, our approach estimates throughput bounds within a few seconds. The evaluation with our prototype on real programs shows that the estimated throughput guarantees are correct with an error of at most 1.7% and provide a tight lower bound for processor- and memory-bottlenecked programs with only 8.5% and 18.2% underestimation.

We introduce the notion of a properly ordered coloring (POC) of a weighted graph, that generalizes the notion of vertex coloring of a graph. Under a POC, if $xy$ is an edge, then the larger weighted vertex receives a larger color; in the case of equal weights of $x$ and $y$, their colors must be different. In this paper, we shall initiate the study of this special coloring in graphs. For a graph $G$, we introduce the function $f(G)$ which gives the maximum number of colors required by a POC over all weightings of $G$. We show that $f(G)=\ell(G)$, where $\ell(G)$ is the number of vertices of a longest path in $G$. Another function we introduce is $\chi_{POC}(G;t)$ giving the minimum number of colors required over all weightings of $G$ using $t$ distinct weights. We show that the ratio of $\chi_{POC}(G;t)-1$ to $\chi(G)-1$ can be bounded by $t$ for any graph $G$; in fact, the result is shown by determining $\chi_{POC}(G;t)$ when $G$ is a complete multipartite graph. We also determine the minimum number of colors to give a POC on a vertex-weighted graph in terms of the number of vertices of a longest directed path in an orientation of the underlying graph. This extends the so called Gallai-Hasse-Roy-Vitaver theorem, a classical result concerning the relationship between the chromatic number of a graph $G$ and the number of vertices of a longest directed path in an orientation of $G$., Comment: To appear in "Order"

International audience; Modern processors raise a challenge for WCET estimation, since detailed knowledge of the processor microarchitecture is not available. This paper proposes a novel hybrid WCET estimation technique, WE-HML, in which the longest path is estimated using static techniques, whereas machine learning (ML) is used to determine the WCET of basic blocks. In contrast to existing literature using ML techniques for WCET estimation, WE-HML (i) operates on binary code for improved precision of learning, as compared to the related techniques operating at source code or intermediate code level; (ii) trains the ML algorithms on a large set of automatically generated programs for improved quality of learning; (iii) proposes a technique to take into account data caches. Experiments on an ARM Cortex-A53 processor show that for all benchmarks, WCET estimates obtained by WE-HML are larger than all possible execution times. Moreover, the cache modeling technique of WE-HML allows an improvement of 65 percent on average of WCET estimates compared to its cache-agnostic equivalent.

In this essay, the new notion concerning longest path is introduced. Longest path has a close relation with the notion of diameter in graph. The classes of graph are studied in the terms of having the vertex with longest path. Valued number is the number of edges belong to the longest path in the matter of vertex. For every vertex, there’s a valued number and new notion of valued set is the generalization of valued number for the vertex when all vertices of the graphs are corresponded to a vertex which has the greater valued number. For any positive integer, there’s one graph in that, there’s vertex which its valued number is that. By deleting the vertices which don’t belong to valued set, new notion of new graph is up. It’s called valued graph. The comparison amid valued graph and initial graph is up, too.

We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that $2$-connected graphs admit sublinear longest cycle transversals., Comment: A previous version of this arXiv post has been split into two parts; this is the first of the two parts

Motivated by kidney exchange, we study the following mechanism-design problem: On a directed graph (of transplant compatibilities among patient-donor pairs), the mechanism must select a simple path (a chain of transplantations) starting at a distinguished vertex (an altruistic donor) such that the total length of this path is as large as possible (a maximum number of patients receive a kidney). However, the mechanism does not have direct access to the graph. Instead, the vertices are partitioned over multiple players (hospitals), and each player reports a subset of her vertices to the mechanism. In particular, a player may strategically omit vertices to increase how many of her vertices lie on the path returned by the mechanism. Our objective is to find mechanisms that limit incentives for such manipulation while producing long paths. Unfortunately, in worst-case instances, competing with the overall longest path is impossible while incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes cannot increase a player's utility by more than a factor of $1 + o(1)$. We therefore adopt a semi-random model where a small ($o(n)$) number of random edges are added to worst-case instances. While it remains impossible for truthful mechanisms to compete with the overall longest path, we give a truthful mechanism that competes with a weaker but non-trivial benchmark: the length of any path whose subpaths within each player have a minimum average length. In fact, our mechanism satisfies even a stronger notion of truthfulness, which we call matching-time incentive compatibility. This notion of truthfulness requires that each player not only reports her nodes truthfully but also does not stop the returned path at any of her nodes in order to divert it to a continuation inside her own subgraph., Full version of EC'21 paper

Recent trends in high performance SoCs (System-on-Chips) indicate a significant growth in memory content causing memory paths to be amongst the most critical paths in the designs. Hence, high quality memory interface tests are crucial in achieving low DPPM (defective parts per million) and better screening of parts. Shared bus interface is a typical memory architecture used in complex processor cores to enable memory testing along its true functional access path. In spite of that, certain gaps exist which limits covering all functional interfaces to memories in its entirety. In this paper, we propose a novel methodology to strategically identify specific high speed memory interfaces with test quality gaps and tactically target them through structural scan based tests along the longest path to enable screen for marginal defects. The proposed method deploys a composite slack based test method to achieve high test quality at a minimal test cost impact. Experimental results on a large design indicate significant reduction (67%) in the target fault set, which resulted in 65% reduction in test vectors (71% test time reduction) using the proposed schemes as compared to baseline methods used for structural memory sequential test.

Accurate neuron morphologies are paramount for computational model simulations of realistic neural responses. Over the last decade, the online repository NeuroMorpho.Org has collected over 140,000 available neuron morphologies to understand brain function and promote interaction between experimental and computational research. Neuron morphologies describe spatial aspects of neural structure; however, many of the available morphologies do not contain accurate diameters that are essential for computational simulations of electrical activity. To best utilize available neuron morphologies, we present a set of equations that predict dendritic diameter from other morphological features. To derive the equations, we used a set of NeuroMorpho.org archives with realistic neuron diameters, representing hippocampal pyramidal, cerebellar Purkinje, and striatal spiny projection neurons (SPNs). Each morphology is separated into initial, branching children, and continuing nodes. Our analysis reveals that the diameter of preceding nodes, Parent Diameter, is correlated to diameter of subsequent nodes for all cell types. Branching children and initial nodes each required additional morphological features to predict diameter, most commonly path length to soma and longest path to terminal end. Model simulations reveal that membrane potential response with predicted diameters was similar to the original response for several tested morphologies. Predictions that use the original diameter of initial nodes improved the membrane potential response, so that the difference from the simulations of the original morphology was reduced to an average of 20%. We provide our open source software to extend the utility of available NeuroMorpho.org morphologies, and suggest predictive equations may supplement morphologies that lack dendritic diameter and improve model simulations with realistic dendritic diameter.

A graph is formed by a pair of vertices and edges. It can be related to groups by using the groups’ properties for its vertices and edges. The set of vertices of the graph comprises the elements or sets from the group while the set of edges of the graph is the properties and condition for the graph. A conjugacy class of an element is the set of elements that are conjugated with . Any element of a group , labelled as , is conjugated to if it satisfies for some elements in with its inverse . A conjugacy class graph of a group is defined when its vertex set is the set of non-central conjugacy classes of . Two distinct vertices and are connected by an edge if and only if their cardinalities are not co-prime, which means that the order of the conjugacy classes of and have common factors. Meanwhile, a simple graph is the graph that contains no loop and no multiple edges. A complete graph is a simple graph in which every pair of distinct vertices is adjacent. Moreover, a -group is the group with prime power order. In this paper, the conjugacy class graphs for some non-abelian 3-groups are determined by using the group’s presentations and the definition of conjugacy class graph. There are two classifications of the non-abelian 3-groups which are used in this research. In addition, some properties of the conjugacy class graph such as the chromatic number, the dominating number, and the diameter are computed. A chromatic number is the minimum number of vertices that have the same colours where the adjacent vertices have distinct colours. Besides, a dominating number is the minimum number of vertices that is required to connect all the vertices while a diameter is the longest path between any two vertices. As a result of this research, the conjugacy class graphs of these groups are found to be complete graphs with chromatic number, dominating number and diameter that are equal to eight, one and one, respectively.

The CPM (Critical Path Method) is a network-based approach for project management. This method identifies the longest path, which allows us to find the critical path that must be shortened so that the completion time of the whole project can be shortened. However, considering uncertainty in CPM is not straightforward. In this paper, we consider an optimization problem for stochastic CPM problems, where task durations are expressed as discrete histograms obtained from historical operation data, that maximizes the probability that all tasks are completed within a given completion time by improving the task durations on the critical path. We propose two reformulations of the problem as a mixed-integer linear programming problem: one based on tasks, and the other based on paths. In addition, we propose an iterative method to solve the problem efficiently by reducing the number of binary variables. Finally, we demonstrate efficiency of our proposed methods in some case studies.

The distributed nature of policy violations in spectrum sharing necessitate the use of mobile autonomous agents (e.g., UAVs, self-driving cars, and crowdsourcing) to implement cost-effective enforcement systems. We define this problem as multiagent planning with cardinality (MPC), where cardinality represents multiple, unique agents visiting each infraction location to collectively improve the accuracy of the enforcement tasks. Designed as a practical and deployable system, our solution leverages crowdsourced information to determine the optimum cardinality and provide a routing schedule for the agents to achieve the desired level of accuracy of detection and localization at minimum possible cost. We show that by estimating spatial orientation of the agents with single antenna, the accuracy is improved by 96% over crowdsourcing only. Using geographical maps as the basis, we solve the scheduling problem with a 3-approximation ratio in polynomial time that exhibits statistically similar performance under variety of urban locale across multiple continents. The longest path traversed by an agent on average is 1.2 km per unit diagonal length of a rectangular geographic area, even when there are twice as many infractions as agents. Deploying UAVs to the estimated region of infraction improves localization accuracy by ≈70% compared to ground vehicles.

The longest path problem is known to be NP-hard. Moreover, they cannot be approximated within a constant ratio, unless ${\rm P=NP}$. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum.In this paper we investigate the performance of an approximation algorithm for this problem in almost every case. We show that a simple algorithm, based on depth-first search, finds on almost every undirected graph $G=(V,E)$ a path of length more than $|V|-3\sqrt{|V| \log |V|}$ and so has performance ratio less than $1+4\sqrt{\log |V|/|V|}$.\

Coloring of mixed graphs that contain both directed arcs and undirected edges is relevant for scheduling of unit-length jobs with precedence constraints and conflicts. The classic GHRV theorem (attributed to Gallai, Hasse, Roy, and Vitaver) relates graph coloring to longest paths. It can be extended to mixed graphs. In the present paper we further extend the GHRV theorem to weighted mixed graphs. As a byproduct this yields a kernel and a parameterized algorithm (with the number of undirected edges as parameter) that is slightly faster than the brute-force algorithm. The parameter is natural since the directed version is polynomial whereas the undirected version is NP-complete. Furthermore we point out a new polynomial case where the edges form a clique.

This paper proposes an algorithm called the Maximum Length Recalculation Algorithm (MLRA) to update the length of the longest path to affected nodes in a perturbed Directed Acyclic Graphs (DAG) where multiple edges are simultaneously deleted and added. MLRA can find all these lengths through a single pass. It is mathematically proved that MLRA is correct. MLRA can be applied in different fields where problems can be described as a perturbed DAG. For instance, this paper applies MLRA on the scheduling problem.