A Theorem on Boolean Matrices

DOI10.1145/321105.321107zbMath0118.33104OpenAlexW2104734478WikidataQ56170979 ScholiaQ56170979MaRDI QIDQ5729523

Stephen Warshall

Publication date: 1962

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321105.321107

zbMATH Keywords

numerical analysis

Related Items (only showing first 100 items - show all)

An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs ⋮ On the optimality of Bellman-Ford-Moore shortest path algorithm ⋮ Dynamic programming and graph optimization problems ⋮ An efficient database transitive closure algorithm ⋮ Detecting causal relationships in distributed computations: In search of the holy grail ⋮ A non-recursive algorithm for classifying the states of a finite Markov chain ⋮ Fast algorithms for the maximum convolution problem ⋮ Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture ⋮ Abstract derivation of transitive closure algorithms ⋮ Parallel and sequential computation on Boolean networks ⋮ Simulated annealing and tabu search approaches to unidirectional flowpath design for automated guided vehicle systems ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ Greedy can beat pure dynamic programming ⋮ Transitive closure and related semiring properties via eliminants ⋮ Periodic sets of integers ⋮ Proof versus formalization ⋮ Experiments with parallel algorithms for combinatorial problems ⋮ Inverse problems of demand analysis and their applications to computation of positively-homogeneous Konüs-Divisia indices and forecasting ⋮ A multi-criteria police districting problem for the efficient and effective design of patrol sector ⋮ Truck routing and scheduling ⋮ Designing networks with compact routing tables ⋮ The input/output complexity of transitive closure ⋮ A branch-and-bound algorithm for the acyclic partitioning problem ⋮ A cutting plane algorithm for the site layout planning problem with travel barriers ⋮ Computing matrix period in max--min algebra ⋮ Searching among intervals and compact routing tables ⋮ Shortest shortest path trees of a network ⋮ k-optimal solution sets for some polynomially solvable scheduling problems ⋮ Graph-based decision for Gödel-Dummett logics ⋮ The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and Experimental evaluation ⋮ Solving linear, min and max constraint systems using CLP based on relational interval arithmetic ⋮ On tropical fractional linear programming ⋮ Crossover can provably be useful in evolutionary computation ⋮ Dijkstra, Floyd and Warshall meet Kleene ⋮ Finite sets of data compatible with multidimensional inequality measures ⋮ Evolutionary synthesis of low-sensitivity digital filters using adjacency matrix ⋮ Finding the shortest paths by node combination ⋮ A sensitive transitive closure algorithm ⋮ A new algorithm to find the shortest paths between all pairs of nodes ⋮ A job-shop problem with one additional resource type ⋮ Combining relational calculus and the Dijkstra-Gries method for deriving relational programs ⋮ Computing orbit period in max-min algebra ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ An all-pairs shortest path algorithm for bipartite graphs ⋮ Quantifying the multi-scale performance of network inference algorithms ⋮ Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem ⋮ Polynomial algorithms to finite Veber problem for a tree network ⋮ The computational complexity of rationalizing Pareto optimal choice behavior ⋮ Formal study of functional orbits in finite domains ⋮ Linear matrix period in max-plus algebra ⋮ Incremental closure for systems of two variables per inequality ⋮ Computing the \(k\)-metric dimension of graphs ⋮ Lock-free parallel dynamic programming ⋮ Shortest path and closure algorithms for banded matrices ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ A note on testing axioms of revealed preference ⋮ Processing time-dependent shortest path queries without pre-computed speed information on road networks ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ Special cases of the quadratic shortest path problem ⋮ Automatic generation of path conditions for concurrent timed systems ⋮ Revealed preference theory: an algorithmic outlook ⋮ Easy and optimal queries to reduce set uncertainty ⋮ On the calculation of transitive reduction-closure of orders ⋮ Lattice flows in networks ⋮ An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses ⋮ The limit behaviour of imprecise continuous-time Markov chains ⋮ Consistent union and prioritized consistent union: new operations for preference aggregation ⋮ Partitioning, tearing and modification of sparse linear systems ⋮ YinYang bipolar logic and bipolar fuzzy logic ⋮ Thick 2D relations for document understanding ⋮ Complete operator precedence ⋮ A cascade algorithm for the logical closure of a set of binary relations ⋮ A spectral approach to the shortest path problem ⋮ Computational experiences with some transitive closure algorithms ⋮ Consistency in networks of relations ⋮ On the complexity of some extended word problems defined by cancellation rules ⋮ On computing the transitive closure of a relation ⋮ Algebraic structures for transitive closure ⋮ An algebraic framework for minimum spanning tree problems ⋮ The ELL(1) parser generator and the error recovery mechanism ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Polyadic dynamic logics for HPSG parsing ⋮ Facilities layout generalized model solved by n-boundary shortest path heuristics ⋮ An efficient algorithm for finding ideal schedules ⋮ Matrix period in max-algebra ⋮ Extensions of the prudence principle to exploit a valued outranking relation ⋮ Dynamic programming bi-criteria combinatorial optimization ⋮ Minimization algorithms for sequential transducers ⋮ An improved transitive closure algorithm ⋮ Sorting can exponentially speed up pure dynamic programming ⋮ Networks of constraints: Fundamental properties and applications to picture processing ⋮ A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) ⋮ A computational procedure for the asymptotic analysis of homogeneous semi-Markov processes ⋮ Transitive reduction of a nilpotent Boolean matrix ⋮ Computing transitive closure on systolic arrays of fixed size ⋮ On negative cycles in mixed graphs ⋮ Computationally efficient sup-t transitive closure for sparse fuzzy binary relations ⋮ A cutting plane method for solving harvest scheduling models with area restrictions ⋮ Regular algebra applied to language problems

This page was built for publication: A Theorem on Boolean Matrices