A Theorem on Boolean Matrices
From MaRDI portal
Publication:5729523
DOI10.1145/321105.321107zbMath0118.33104OpenAlexW2104734478WikidataQ56170979 ScholiaQ56170979MaRDI QIDQ5729523
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
Related Items
Relation algebra with multi-relations, PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS, The Boolean pivot operation, \(M\)-matrices, and reducible matrices, [https://portal.mardi4nfdi.de/wiki/Publication:5558934 Eine Bemerkung zum Tripel-Algorithmus zur Bestimmung der k�rzesten Wege in einem Graphen], Shortest‐path methods: Complexity, interrelations and new propositions, Efficient transitive closure of sparse matrices over closed semirings, The index of primitivity of a non-negative matrix, Dioïds and semirings: Links to fuzzy sets and other applications, Euclidean distance matrix completion problems, Efficient parallel algorithms for shortest paths in planar graphs, Searching among intervals and compact routing tables, A transitive closure algorithm, Simple Rectangle-Based Functional Programs for Computing Reflexive-Transitive Closures, Faster All-Pairs Shortest Paths via Circuit Complexity, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, On the route construction in changing environments using solutions of the eikonal equation, Parallel decision procedures for finite state automata, Maximal and Maximum Transitive Relation Contained in a Given Binary Relation, Temporal Structures, Solving all-pairs shortest path by single-source computations: theory and practice, Multicriteria problems with importance-ordered criteria groups, Order batching using an approximation for the distance travelled by pickers, No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines, Some problems in discrete optimization, Incremental versus non-incremental dynamic programming, Computing revealed preference goodness-of-fit measures with integer programming, Efficient parameterized algorithms for computing all-pairs shortest paths, Minimum gradation in greyscales of graphs, Quantifying the Discord: Order Discrepancies in Message Sequence Charts, The computational complexity of rationalizing boundedly rational choice behavior, Testable implications of general equilibrium models: an integer programming approach, Balancing of manufacturing systems with complex configurations for delayed product differentiation, Extensions of dynamic programming for multi-stage combinatorial optimization, On the Optimal Control of Boolean Control Networks, Universal construction mechanism for networks from one-dimensional symbol sequences, Computational Complexity of SRIC and LRIC Indices, Applications of graph theory in computer systems, Bounds on maximum concurrent flow in random bipartite graphs, Shortest path network problems with stochastic arc weights, QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS, The idemetric property: when most distances are (almost) the same, Planning temporal events using point-interval logic, Solving an urban waste collection problem using ants heuristics, On pure structure of dynamic systems, Precedence parsing using domolki's algorithm, Shortest-path queries in static networks, Model checking propositional dynamic logic with all extras, A simplified test for preference rationality of two-commodity choice, TWO ALGORITHMS FOR FAST INCREMENTAL TRANSITIVE CLOSURE OF SPARSE FUZZY BINARY RELATIONS, Communication lower bounds and optimal algorithms for numerical linear algebra, A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices, Unary algebras without proper subalgebras, Bi-criteria path problem with minimum length and maximum survival probability, Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments, As Close as It Gets, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices, Managing consensus based on leadership in opinion dynamics, Unnamed Item, Random matrices and graphs, Indexing Structure for Graph-Structured Data, Approximation Limitations of Pure Dynamic Programming, A review and proposal of (fuzzy) clustering for nonlinearly separable data, Solving the Nearly Symmetric All-Pairs Shortest-Path Problem, Efficient single-pair all-shortest-path query processing for massive dynamic networks, OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations, Generating all vertices of a polyhedron is hard, Fine-Grained Complexity Theory (Tutorial), Efficient determination of the transitive closure of a directed graph, ENFORCING CONCURRENT TEMPORAL BEHAVIORS, Tropical Complexity, Sidon Sets, and Dynamic Programming, Multi-scale transition matrix approach to time series, On shortest-path algorithms in the topological design of computer networks: a comparative study, Automata and rational expressions, Improved distance queries and cycle counting by Frobenius normal form, Minimal distance of propositional models, \({\mathfrak R}\)-Netzwerke und Matrixalgorithmen, On computing the time complexity of transitive closure algorithms, Fast and parallel decomposition of constraint satisfaction problems, Local orthogonal bases. II: Window design, Unnamed Item, Optimal systolic array algorithms for tensor product, ALGORITHMS FOR FINDING CHOMSKY AND GREIBACH NORMAL FORMS FOR A FUZZY CONTEXT‐FREE GRAMMAR USING AN ALGEBRAIC APPROACH, An efficient algorithm for finding kleene closure of regular expression matrices, Incrementally closing octagons, Nonlocal pagerank, From Circuit Complexity to Faster All-Pairs Shortest Paths, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, How to Keep an Eye on Small Things, Finding a minimum equivalent graph of a digraph, Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time, An algorithm for computing all paths in a graph, An approach for efficient ship routing, Revealed preference tests for weak separability: an integer programming approach, Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures, Extreme points of the credal sets generated by comparative probabilities, Closing reciprocal relations w.r.t. stochastic transitivity, Revealed preference theory for finite choice sets, THE TRANSITIVE CLOSURE AND RELATED ALGORITHMS OF DIGRAPH ON THE RECONFIGURABLE ARCHITECTURE, A comparison of gaussian and gauss-jordan elimination in regular algebra, 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, Topological reduction approaches for relation decision systems, Abstract interpretation of graphs, Shortest distances as enumeration problem, An ‘All pairs shortest paths’ distributed algorithm using 2n 2 messages, A clustering- and maximum consensus-based model for social network large-scale group decision making with linguistic distribution, Transitive closure algorithms for very large databases, Sensitivity of fair prices in assignment markets
