Abstract The eccentricity lowering problem is to reduce the eccentricity of a network by upgrading some nodes (that is, shrinking the lengths of the edges incident to such nodes). We consider two types of node‐upgrading strategies, that is, a continuous upgrading strategy and a discrete upgrading strategy, where the improvement under the first strategy is a continuous variable, and the improvement under the second strategy is a fixed amount. These problems are hard even to approximate, for general graphs. Therefore, we restrict our attention to graphs with simple structures. Assuming that the graph G = (V,E) is a tree, we show that the eccentricity lowering problem under the continuous node‐upgrading strategy can be reduced to the eccentricity lowering problem under the continuous edge‐upgrading strategy, and can be solved by an O(|V| log |V|) time algorithm. We also show that the problem for a tree is NP‐hard under the discrete upgrading strategy, but admits a fully polynomial approximation scheme, if the graph is a line. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 232–239 2005

We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an adaptive mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational results on benchmark instances of small sizes show that the method obtains solutions that are optimal or that deviate by at most 0.16% from the best known solutions. Comparisons with other approaches from the literature show that, for instances of larger sizes, our method obtains the best solutions among all heuristics tested.

Abstract We consider two variants of the single‐vehicle scheduling problem on line‐shaped networks. Let L = (V, E) be a line, where V = {v1, v2, … , vn} is a set of n vertices and E = {{vi, vi+1}|i = 1, 2, … , n − 1} is a set of edges. The travel times w(u, v) and w(v, u) are associated with each edge {u, v} ∈ E, and each job, which is also denoted as v and is located at vertex v ∈ V, has release time r(v) and handling time h(v). There is a single vehicle, which is initially situated at v1 ∈ V, and visits all vertices to process the jobs before it returns back to v1. The first problem asks to find an optimal routing schedule of the vehicle that minimizes the completion time. This is NP‐hard [21], and there exists an approximate algorithm with the approximation ratio of 2 [12]. In this paper, we improve this ratio to 1.5. On the other hand, the second problem minimizes the maximum lateness, under the assumption that all release times r(v) are zero, but there are due times d(v) for v ∈ V and d(vn+1) for the vehicle. This problem is also NP‐hard [13]. We improve the previous best‐known approximation ratio of 2, which was obtained in [11], to 1.5. © 2002 Wiley Periodicals, Inc.

Abstract Given an undirected multigraphG= (V,E) and a requirement functionrλ: ( ) →Z+(where ( ) is the set of all pairs of vertices andZ+is the set of nonnegative integers), we consider the problem of augmentingGby the smallest number of new edges so that the local edge‐connectivity and vertex‐connectivity between every pairx,y∈Vbecome at leastrλ(x,y) and two, respectively. In this paper, we show that the problem can be solved inO(n3(m+n) log(n2/(m+n))) time, wherenandmare the numbers of vertices and pairs of adjacent vertices inG, respectively. This time complexity can be improved toO((nm+n2logn) logn), in the case of the uniform requirementrλ(x,y)= 𝓁 for allx,y∈V. Furthermore, for the generalrλ, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed 𝓁*= max{rλ(x,y) |x,y∈V}. © 2001 John Wiley & Sons, Inc.

In this paper, we study issues on disjunctions of propositional Horn theories. In particular, we consider the problems of deciding whether a disjunction of Horn theories is Horn, and, if not, computing a Horn core (i.e., a maximal Horn theory included in this disjunction) and the Horn envelope (i.e., the minimum Horn theory including the disjunction), where a Horn core and the Horn envelope are important approximations of the original theory in artificial intelligence. The problems are investigated for two different representations of Horn theories, namely, for Horn conjunctive normal forms (CNFs) and characteristic models. While the problems are shown to be intractable in general, in the case of bounded disjunctions, we present polynomial time algorithms for testing the Horn property in both representations and for computing a Horn core in the CNF representation. Even in the case of bounded disjunction, no polynomial algorithm exists (unless P=NP) for computing a Horn core in the characteristic model representation. Computing the Horn envelope is polynomial in the characteristic model representation, while it is exponential in the CNF representation, even for bounded disjunction.

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

Given a partially defined Boolean function (pdBf) (T,F), we investigate in thispaper how to find a Horn extension $f: \{0,1\}^n \mapsto \{0,1\}$, which is consistent with (T,F), where $T \subseteq \{0,1\}^n$ denotes a set of true Boolean vectors (or positive examples) and $F \subseteq \{0,1\}^n$ denotes a set of false Boolean vectors (or negative examples). Given a pdBf (T,F), it is known that the existence of a Horn extension can be checked in polynomial time. As there are many Horn extensions, however, we consider those extensions f which have maximal and minimal sets T(f) of the true vectors of f, respectively. For a pdBf (T,F), there always exists the unique maximal (i.e., maximum) Horn extension, but there are in general many minimal Horn extensions. We first show that a polynomial time membership oracle can be constructed for the maximum extension, even if its disjunctive normal form (DNF) can be very long. Our main contribution is to show that checking if a given Horn DNF represents a minimal extension and generating a Horn DNF of a minimal Horn extension can both be done in polynomial time. We also can check in polynomial time if a pdBf (T,F) has the unique minimal Horn extension. However, the problems of finding a Horn extension f with the smallest |T(f)| and of obtaining a Horn DNF, whose number of literals is smallest, are both NP-hard.

Let G be an Eulerian digraph, and let {x1, x2}, {y1,y2} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x1, x2}, {y1,y2}) is called feasible if there is a choice of h,i,j,k with {h,i} = {j,k} = {1,2} such that G has two arc-disjoint xhxi- and yjyk-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m+nlog n) time algorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m+nlog n)) time.

The ATM switching scheme we propose is similar to the multi-frame stop-and-go, except that we use EDF (earliest-deadline-first) scheduling, instead of rate-monotonic, static-priority scheduling. Unlike the multi-frame stop-and-go, our scheme can fully utilize the link bandwidth, and does not require that the input or output frames of the same size be synchronized. EDF scheduling is, in general, more complex than static-priority scheduling. However, we show that the next earliest deadline needs to be computed only when an output frame reaches its end, i.e., not whenever a cell is output, resulting in significant saving in computation time. We derive bounds on end-to-end delay and delay-jitter, and discuss implementation issues.

We consider the problem of identifying an unknown Boolean function f by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that f is a positive (or monotone) function of n variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in n and m, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of f. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function f of n variables, decide whether or not f is 2-monotonic and, if f is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.

Consider the problem of identifying $\min T(f)$ and $\max F(f)$ of a positive (i.e., monotone) Boolean function f by using membership queries only, where $\min T(f)\,(\max F(f))$ denotes the set of minimal true vectors (maximal false vectors) of f. It is known that an incrementally polynomial algorithm exists if and only if there is a polynomial time algorithm to check the existence of an unknown vector u for given sets $MT \subseteq \min T(f)$ and $MF \subseteq \max F(f)$; that is, $u \in \{0,1\}^n \setminus (\{v | v \geq w {\rm for some } w \in MT \} \cup \{v | v \leq w {\rm for some } w \in MF \})$. This paper introduces a measure for the difficulty to find an unknown vector, which is called the maximum latency. If the maximum latency is constant, then an unknown vector can be found in polynomial time and there is an incrementally polynomial algorithm for identification. Several subclasses of positive functions are shown to have constant maximum latency, e.g., 2-monotonic positive functions, $\Delta$-partial positive threshold functions, and matroid functions, while the class of general positive functions has $\lfloor n/4 \rfloor +1$ maximum latency and the class of positive k-DNF functions has $\Omega (\sqrt{n})$ maximum latency.

Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and n and m denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k < \four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.

Article Free Access Share on Deterministic Õ(nm) time edge-splitting in undirected graphs Authors: Hiroshi Nagamochi Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01 Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01View Profile , Toshihide Ibaraki Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01 Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01View Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 64–73https://doi.org/10.1145/237814.237830Published:01 July 1996Publication History 7citation291DownloadsMetricsTotal Citations7Total Downloads291Last 12 Months16Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A coterie, which is used to realize mutual exclusion in a distributed system is a family C of incomparable subsets such that every pair of subsets in C has at least one element in common. Associate with a family of subsets C a positive (i.e., monotone) Boolean function f/sub c/ such that f/sub c/(x)=1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f/sub c/ is dual-minor, and is a nondominated (ND) coterie if and only if f/sub c/ is self-dual. We introduce an operator /spl rho/, which transforms a positive self-dual function into another positive self-dual function, and the concept of almost-self-duality, which is a close approximation to self-duality and can be checked in polynomial time (the complexity of checking positive self-duality is currently unknown). After proving several interesting properties of them, we propose a simple algorithm to check whether a given positive function is self-dual or not. Although this is not a polynomial algorithm, it is practically efficient in most cases. Finally, we present an incrementally polynomial algorithm that generates all positive self-dual functions (ND coteries) by repeatedly applying p operations. Based on this algorithm, all ND coteries of up to seven variables are computed.>

Asynchrony (due to unknown message transmission delay) complicates the design of protocols for distributed systems. To simplify the protocol design task therefore, the authors propose an interprocess (point-to-point) communication mechanism that has the characteristic of instantaneous message passing. They first establish a hierarchy among synchronization properties, which shows that to ensure the logically instantaneous message passing property it is not always necessary to use a rendezvous mechanism. Next, they propose a solution to the logically instantaneous message passing problem that is more efficient than R. Bagrodia's (1989) rendezvous and K.J. Goldman's (1991) logically synchronous multicast in the point-to-point (single-cast) setting. This algorithm has the following properties: it is applicable without deadlock to the partner model in which each process acts as both client and server; it requires three control messages to send an application message, which is shown to be quasioptimum message complexity; and its worst-case response time from a send request to the occurrence of the corresponding send event is 2k/spl Delta/ (sec.), where k is the maximum number of interfering send requests and /spl Delta/ (sec.) is an assumed upper bound on interprocess communication delay. Furthermore, two modified algorithms are proposed: one for reducing the number of control messages required for an application message, and the other for attaining a shorter average response time by using a randomization technique.>

A coterie under a ground set U consists of subsets (called quorums) of U such that any pair of quorums intersect with each other. Nondominated (ND) coteries are of particular interest, since they are optimal in some sense. By assigning a Boolean variable to each element in U, a family of subsets of U is represented by a Boolean function of these variables. The authors characterize the ND coteries as exactly those families which can be represented by positive, self-dual functions. In this Boolean framework, it is proved that any function representing an ND coterie can be decomposed into copies of the three-majority function, and this decomposition is representable as a binary tree. It is also shown that the class of ND coteries proposed by D. Agrawal and A. El Abbadi (1989) is related to a special case of the above binary decomposition, and that the composition proposed by M.L. Neilsen and M. Mizuno (1992) is closely related to the classical Ashenhurst decomposition of Boolean functions. A number of other results are also obtained. The compactness of the proofs of most of these results indicates the suitability of Boolean algebra for the analysis of coteries.>

Although finding an optimal coterie for a general graph G is computationally intractable, it is shown that it can be easily found if G is a ring. Since the solution is already known when G is a complete graph, it is implied that an optimal coterie can be obtained if every biconnected component of G consists of a single edge, a ring, or a complete graph.>

Given an undirected graph $G = ( V,E )$, it is known that its edge-connectivity $\lambda ( G )$ can be computed by solving $O( | V | )$ max-flow problems. The best time bounds known for the problem are $O( \lambda ( G ) | V |^2 )$, due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and $O( | E |^{3/2} | V | )$, due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple. An $O( | E | + \min \{ \lambda ( G ) | V |^2 ,p | V | + | V |^2 \log | V | \} )$ time algorithm for computing the edge-connectivity $\lambda ( G )$ of a multigraph $G = ( V,E )$, where $p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of $| V |$ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in $O ( | V | | E | + | V |^2 \log | V | )$ time.

Abstract The reliability of capacitated networks subject to random arc failures is evaluated by the expected value of maximum flow. It is known that calculating the expected value of maximum flow is NP‐hard, but a lower bound can be efficiently computed by the method of Carey and Hendrickson. This bound sometimes gives the exact value, e.g., if graphs are bipartite. In this article, for directed and undirected networks, respectively, we give necessary and sufficient conditions for the above lower bound to provide the exact value.

Let G be an Eulerian digraph, and $a,b,c$ an ordered triple of its vertices. A polynomial time algorithm of $O( e + n^2 )$ time is presented to decide whether G contains three arc disjoint $ab$-, $bc$-, and $ca$-paths, where e and n are the numbers of arcs and vertices, respectively. The algorithm is based on a structural characterization of minimal infeasible instances of the problem.

Abstract We study the multicommodity flow problem that minimizes a strictly convex cost objective function subject to the capacity constraints on individual commodities as well as the total flows in each arc. By making use of its dual, we formulate the problem as a nonlinear unconstrained optimization problem and propose relaxation methods. Computational results show that the proposed methods can practically solve problem instances, for example, with up to 100 nodes, 1000 arcs, and seven commodities.

Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence belonging to MC by reordering, if necessary, the incoming sequence of requests from transactions and it never resorts to rollbacks. In the model, transactions on arrival predeclare their read sets and write sets. It is shown that MCS(MWW) and MCS(MWRW) can be executed in polynomial time, where MWW and MWRW are multiversion classes of logs serializable under the write-write and write-read-write constraints respectively. For any multiversion class MC of interest, MCS(MC) does not exhibit cancellation anomaly, i.e. it functions correctly even if some of the predeclared steps are canceled. Furthermore, MCS(MWW) functions correctly, even if transactions issue more read operations than they predeclared. Thus, MCS(MWW) allows each transaction to predeclare only its write set.>

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed.>

This paper deals with the serializability theory for single-version and multiversion database systems. We first introduce the concept of disjoint-interval topological sort ( DITS , for short) of an arc-labeled directed acyclic graph. It is shown that a history is serializable if and only if its transaction IO graph has a DITS. We then define several subclasses of serializable histories, based on the constraints imposed by write-write, write-read, read-write, or read-read conflicts, and investigate inclusion relationships among them. In terms of DITS, we give a sufficient condition for a class of serializable histories to be polynomially recognizable, which is then used to show that a new class of histories, named WRW, can be recognized in polynomial time. We also present NP-completeness results for the problem of testing membership in some other classes. In the second half of this paper, we extend these results to multiversion database systems. The inclusion relationships among multiversion classes defined by constraints, such as write-write and write-read, are investigated. One such class coincides with class DMVSR, introduced by Papadimitriou and Kanellakis, and gives a simple characterization of this class. It is shown that for most constraints, multiversion classes properly contain the corresponding single-version classes. Complexity results for the membership testing are also discussed.

The semijoin provides a means of reducing the amount of data transmission among sites in a distributed database system. Previously the semijoin has been studied mainly for reducing communication cost in an environment with global public communication networks. In a local area system, however, wide bandwidth is usually available and the communication cost is virtually negligible. In view of this, we adopt a simplified model of a local area network, imposing no constraint on the transmission line capacity and the communication processing capability at each site. For this model, an efficient algorithm for obtaining the shortest semijoin schedule, in the sense of minimizing the total number of semijoin transmissions, is developed. It is based on a schedule diagram newly introduced to represent the semijoin schedule.

We propose a new class of schedulers, called cautious schedulers , that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW- scheduling is, in general, NP-complete. Therefore, we introduce a special type ( type 1R ) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.

This paper treats the file redundancy issue in distributed database systems, asking what is the optimal number of file copies, given the ratio r of the frequency of update requests to the frequency of all file access requests (i.e., queries and updates). Formulations of this type of problem, including optimal file allocation, have been attempted by a number of authors, and some algorithms have been proposed. Although such algorithms can be used to solve particular problems, it seems difficult to draw general conclusions applicable to a wide variety of practical distributed database systems. To probe into this hard to formulate but interesting problem, our paper constructs simplified network models of distributed database systems, and computes the optimal number of file copies, as well as their locations, to minimize the communication cost. For several network types, we plot the optimal number of file copies as a function of the ratio r.

Using the nested loops method, this paper addresses the problem of minimizing the number of page fetches necessary to evaluate a given query to a relational database. We first propose a data structure whereby the number of page fetches required for query evaluation is substantially reduced and then derive a formula for the expected number of page fetches. An optimal solution to our problem is the nesting order of relations in the evaluation program, which minimizes the number of page fetches. Since the minimization of the formula is NP-hard, as shown in the Appendix, we propose a heuristic algorithm which produces a good suboptimal solution in polynomial time. For the special case where the input query is a “tree query,” we present an efficient algorithm for finding an optimal nesting order.

Consider a system consisting of a set ofn processes, P~, P2 ..... Pn, and a set of serially reusable resources of m different types, R1, R~ ..... R,~.It is assumed that the system is "claim-limited," that is, its "claim matrix" C, whose (i, j) element C(i, j) is the maximum number of units of R: that may be needed by P, at the same time, is known a priori.It is desired to design a deadlock-free system, that is, one which never deadlocks for any allocation sequence within the limits given by C. For j ffi 1, 2 ..... m, let a, (>0) be the cost of one unit of Rj.An algorithm for designing a deadlock-free system with the minimum resource cost is presented.Its running time is bounded by O(ca(m) + mlogm), where e ts the number of nonzero elements in C and a, is the inverse of Ackermann's function, which is very slowly growing Categories and Subject Descriptors: D.4.m

Abstract This article gives an efficient algorithm for obtaining K shortest simple paths between two specified nodes in an undirected graph G with non‐negative edge lengths. Letting n be the number of nodes and m be the number of edges in G, its running time is O(Kc(n, m)) if the shortest paths from one node to all the other nodes are obtained in c(n, m) [≥O(m)] time, and the required space is O(Kn + m). This time bound is better than those realized by existing algorithms, the best of which, proposed by Yen, requires O(Kn3) time, since c(n, m) ≤min[O(n2), O(m log n)] is known.

Consider a computer system in which different types of serially reusable resources are shared by several classes of processes. We assume that each process in a process class has the same known maximum claim (i.e., the maximum resource requirement), but that the actual sequence of requests is unknown. Our resource manager uses the "expedient policy" in granting requests for resources, under the constraint that at most K (a constant) processes can reside in the system at any time.

An algorithm is presented for obtaining the K best solutions of the resource allocauon problem with an objective function which is the sum of convex functions of one variable It requires O(T* + Klog K + Kn~ogn) time and O(Kn~ogn + n) space, where n is the number of variables and T* ~s the computatmnal time to obtain the best solution KEY WORDS AND PHRASES resource aUocatmn problem, K best soluuons, computational complexity CR CATEGORIES 5 25, 5 30, 5 41 O(Nlogn + n).The method of [27] requires O(c(n, N) + nlogn) time, where c(n, N) is the time required to solve the continuous problem P' obtained from P by dropping the integrality condition on the x,.A third type of approach is exemplified by [6, 7,

This paper presents an algorithm for finding K minimum spanning trees in an undirected graph. The required time is $O(Km + \min (n^2 ,m\log \log n))$ and the space is $O(K + m)$, where n is the number of vertices and m is the number of edges. The algorithm is based on three subroutines. The first two subroutines are used to obtain the second minimum spanning tree in $O(\min (n^2 ,m\alpha (m,n)))$ steps, where $\alpha (m,n)$ is Tarjan’s inverse of Ackermann’s function [12] which is very slowly growing. The third one obtains the kth minimum spanning tree in $O(m)$ steps when the jth minimum spanning trees for $j = 1,2, \cdots ,k - 1$ are given.

Consider a network which can be represented by an acyclic directed graph such that the links represented by the edges are subject to failure. Under the assumption that at most one link can fail at any time, we want to locate a failed link, if any, by means of certain tests. A test is performed by injecting a signal at a vertex and monitoring it at another vertex and can reveal if there is a failed link on any path between the two vertices. We want to find a minimal set of tests that can uniquely locate any single fault. Since this problem is in general NP-complete, we investigate a special case where the given network has a tree structure. We present an algorithm whose worst case running time can be bounded by a linear function of the input size.

A dominance relation D is a binary relation defined on the set of partial problems generated in a branch-and-bound algorithm, such that P i DP j (where P i and P j are partial problems) implies that P j can be excluded from consideration without loss of optimality of the given problem if P i has already been generated when P j is selected for the test. The branch-and-bound computation is usually enhanced by adding the test based on a dominance relation. A dominance relation D′ is said to be stronger than a dominance relation D if P i DP j always implies P i D′P j . Although it seems obvious that a stronger dominance relation makes the resulting algorithm more efficient, counterexamples can easily be constructed. In this paper, however, four classes of branch-and-bound algorithms are found in which a stronger dominance relation always gives a more efficient algorithm. This indicates that the monotonicity property of dominance relations would be observed in a rather wide class of branch-and-bound algorithms, thus encouraging the designer of a branch-and-bound algorithm to find the strongest possible dominance relation.

The above paper1 by Magó discusses the state assignment problem by means of monotone increasing (i.e., positive) next-state functions for both synchronous and asynchronous sequential networks. It may be interesting to note that the same subject for synchronous sequential networks has also been studied under a somewhat different title: "Fail-Safe Realization of Sequential Machines." This is because a realization with positive next-state functions (and positive output functions) results in a fail-safe sequential circuit in a certain sense.

This paper is concerned with the representation of a discrete optimization problem given in the form of a $ddp$ (discrete decision process) by a G-$sdp$ (G-sequential decision process). A G-$sdp$ is a finite state model of discrete optimization problem, consisting of a finite number of states and a rule specifying the transition from one state to another corresponding to each decision applied to it. A cost function, taken from a given family of functions G, is associated with each transition. A necessary and sufficient condition for a given $ddp$ to be represented by a G-$sdp$, which is valid for most important G’s, is obtained ; it turns out that various representation theorems obtained in the earlier paper [3] are special cases of this theorem. Furthermore, a case in which the existence of the unique minimal representation is guaranteed to exist receives special attention, and some sufficient conditions are discussed.

The design of optimal logic networks is formulated as integer programming (IP) problems. This formulation has the following advantages over other methods of logic design. 1) General feed-forward networks can be dealt with rather than two-level or three-level networks usually treated in conventional switching theory. 2) Network restrictions such as fan-in and fan-out restrictions are easily incorporated. 3) Various gate types such as NOR, NAND, AND-OR combination, NOR-AND combination, and those gates with NOR-OR dual outputs can be treated. 4) Various objectives such as the number of gates and the number of connections are minimized. 5) Incompletely specified functions can be handled without additional difficulty. 6) The formulation can be extended to multiple-output networks. To solve the resulting IP problems, the implicit enumeration method of integer programming is found to be suitable. An IP code ILLIP (Illinois Integer Programming Code) is implemented based on the implicit enumeration by incorporating some new gimmicks such as pseudounderlining. Then the ILLIP is used to solve the IP problems for logical design by making use of the inherent structure of our problems. Various optimal networks are derived by a computer as follows: optimal NOR networks and optimal NOR-AND networks for all functions of up through three variables, one-bit adders with various gate types, and others. These results indicate the computational feasibility of the integer programming approach.

Let S be a sequential machine with binary (i. e., 0 or 1) input and binary output. Suppose that the third value N, different from 0 and 1, represents the faulty input or output value. An N-fail-safe (NFS) machine S̄ of S is then defined as a sequential machine with ternary (i.e., 0, 1, or N) input and ternary output such that: 1) S is a submachine of S̄, and 2) possible output failures of S̄ are 0→N or 1→ N for any input failures 0→N or 1→N. This machine may be considered "fail-safe" since no failure such as 0→1 or 1→0 occurs in the output.

In this note, we develop an algorithm to design a two-level switching network composed of negative gates with no fan-in restriction imposed on them. The resulting network is such that it minimizes the cost function h(G, 1), a monotone nondecreasing function of G and I, where G is the total number of gates and I is the total number of interconnections in the network. In other words, the earlier work is generalized so that the number of interconnections may be included in its cost criterion. The algorithm is then extended to the multiple output network design.

In this paper we develop an algorithm to design a switching network using only gates which represent negative functions. The number of gates in the network is minimized under the conditions that 1) the network consists of two levels, and 2) no fan-in restriction on each gate is imposed.

Abstract—As an approach to clarifying the basic properties of threshold logic, the completely monotonic function is investigated. Its testing procedure, functional form, etc., are discussed by using a new concept, mutual monotonicity.

Abstract—The concept of mutual monotonicity developed in the previous paper[1] is applied to the compound synthesis of an arbitrary logic function by a combination of completely monotonic functions or in most cases by threshold functions.

Abstract—A model of autonomous logic nets composed of n threshold elements is presented and several properties of a single threshold element are generalized to this model. The number of these nets is shown to be 2kn³(½≤k≤l) for completely specified machines. The capacity of the net is defined and conjectured to be 2, similar to the case of a single threshold element. P and NPN classifications of the machines are proposed and applied to the enumeration of all periodic sequences of length 2n(n≤4) realizable by this net. The state assignment problem of the net is also treated. The existence of transition diagrams which cannot be realized by this model for any state assignment, or of those that can be realized for any state assignment, is shown, and it turns out that almost all completely specified machines belong to the former class when n is sufficiently large. Considering the synthesis of a net, an application of learning procedure is also discussed and it is pointed out that only periodic sequences of length 2" can be learned automatically.

Threshold functions are a class of Boolean Functions which have been studied for several years under different names such as majority functions, linearly separable functions, and linear input functions.