This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

For a fixed number of nodes, we focus on directed acyclic graphs in which there is not a shortcut. We find the case where the number of paths is maximized and its corresponding count of maximal paths. Considering this case is essential in solving large-scale scheduling problems using a PERT chart.

A method for efficiently representing the state equation in a class of max-plus linear systems is proposed. We introduce a construct referred to as 'cell' in which the list of possible longest paths is stored. By imposing interval constraints on the system parameters, we can reduce the complexity of the state equation. The proposed method would be useful in scheduling applications for systems with adjustable system parameters.

This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband EngineTM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.

This research considers an efficient method for calculating the transition matrix in an MPL (Max-Plus Linear) state-space representation. This matrix can be generated by applying the Kleene star operator to an adjacency matrix. The proposed method, based on the idea of a topological sort in graph theory and block splitting, is able to calculate the transition matrix efficiently.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.

All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.

In Asiacrypt '96, Bleichenbacher et al. showed the upper limit of the efficiency of one-time digital signature scheme using a directed graph of tree structure as its base. They also claimed that there exists more effective signature scheme on general directed graphs, and showed an example of a method to construct more effective signature schemes as a witness. Unfortunately, their example does not achieve the efficiency as they claimed. This paper shows the upper limit of the efficiency of the signature scheme on general directed graphs by showing no signature scheme is more effective than the optimal signature scheme on trees (or forests). Further, we introduce another signature scheme named pseudo k-time signature scheme. This signature scheme allows signers to sign k-time which is no less efficient than the one time signature scheme.

We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.