The Transitive Reduction of a Directed Graph

DOI10.1137/0201008zbMath0247.05128OpenAlexW2110920860WikidataQ56699883 ScholiaQ56699883MaRDI QIDQ5659571

A. V. Aho, Michael R. Garey, Jeffrey D. Ullman

Publication date: 1972

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d0be1e20643e7e15bd4669f1c3ef0c2287852566

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

A Sequential Importance Sampling Algorithm for Counting Linear Extensions, Semicomplete compositions of digraphs, Relativized adjacency, Computing consensus networks for collections of 1-nested phylogenetic networks, Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples, Morphological hierarchies: a unifying framework with new trees, GRASP‐ILS and set cover hybrid heuristic for the synchronized team orienteering problem with time windows, Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items, Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling, Capturing complexity over space and time via deep learning: an application to real-time delay prediction in railways, Capacity-preserving subgraphs of directed flow networks, An algorithmic metatheorem for directed treewidth, A compact labelling scheme for series-parallel graphs, Representation and management of MOEA populations based on graphs, What is the dimension of citation space?, Heuristic solutions for the vehicle routing problem with time windows and synchronized visits, A verified algorithm enumerating event structures, On familywise type I error control for multiplicity in equivalence trials with three or more treatments, Cycle analysis of directed acyclic graphs, The complexity of Boolean matrix root computation, Computing unique canonical covers for simple FDs via transitive reduction, FCA2VEC: Embedding Techniques for Formal Concept Analysis, Scalable Visual Analytics in FCA, A linear algorithm to decompose inheritance graphs into modules, Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness, Approximating Transitive Reductions for Directed Networks, Solving an integrated cell formation and group layout problem using a simulated annealing enhanced by linear programming, An adaptive large neighbourhood search for asset protection during escaped wildfires, A model of language learning with semantics and meaning-preserving corrections, Tree structure for distributive lattices and its applications, Maximal and Maximum Transitive Relation Contained in a Given Binary Relation, SEPARATION NUMBERS WITH RESPECT TO SQUARE NUMBERS, Mincut sensitivity data structures for the insertion of an edge, On algorithmic Coxeter spectral analysis of positive posets, Estimating an extreme Bayesian network via scalings, Uniform random posets, Poincaré polynomials of generic torus orbit closures in Schubert varieties, An exact dynamic programming algorithm for the precedence-constrained class sequencing problem, On strongly connected digraphs with bounded cycle length, Minimum equivalent precedence relation systems, Best match graphs, Fault-tolerant control for a class of linear interconnected hyperbolic systems by boundary feedback, Stable allocations and partially ordered sets, Complexité de problèmes liés aux graphes sans circuit, Variable symmetry breaking in numerical constraint problems, Provably-secure time-bound hierarchical key assignment schemes, Optimum cuts in graphs by general fuzzy connectedness with local band constraints, Exact and fully symbolic verification of linear hybrid automata with large discrete state spaces, Max-linear models on directed acyclic graphs, Finding strong bridges and strong articulation points in linear time, Dynamic maintenance of directed hypergraphs, Solutions for subset sum problems with special digraph constraints, LP-structures analysis: substantiation of refactoring in object-oriented programming, Counting independent sets in cocomparability graphs, Toric Bruhat interval polytopes, Inferring (biological) signal transduction networks via transitive reductions of directed graphs, A Comparison of Random Task Graph Generation Methods for Scheduling Problems, Mincut Sensitivity Data Structures for the Insertion of an Edge, Efficient CNF Simplification Based on Binary Implication Graphs, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, Directed hypergraphs: introduction and fundamental algorithms -- a survey, How to use the minimal separators of a graph for its chordal triangulation, Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization, New constructions for provably-secure time-bound hierarchical key assignment schemes, On the complexity of strongly connected components in directed hypergraphs, On the calculation of transitive reduction-closure of orders, Ergodic properties of folding maps on spheres, Minimal equivalent subgraphs containing a given set of arcs, Foundations of semantic web databases, Join-reachability problems in directed graphs, Efficiently Representing Existential Dependency Sets for Expansion-based QBF Solvers, The Secret Life of Keys: On the Calculation of Mechanical Lock Systems, Upside-Down Preference Reversal: How to Override Ceteris-Paribus Preferences?, Generic torus orbit closures in Schubert varieties, Transitive-Closure Spanners: A Survey, Computational experiences with some transitive closure algorithms, Efficient provably-secure hierarchical key assignment schemes, Reduction of a nilpotent fuzzy matrix, Rank tests from partially ordered data using importance and MCMC sampling methods, Graph-intersecting set systems and LYM inequalities, The Role of Structural Reasoning in the Genesis of Graph Theory, Improved Guarantees for Vertex Sparsification in Planar Graphs, The minimum spanning strong subdigraph problem is fixed parameter tractable, The stable \(b\)-matching polytope revisited, Supporting dynamic updates in storage clouds with the Akl-Taylor scheme, Unnamed Item, Learning large-alphabet and analog circuits with value injection queries, On the Relations Between Security Notions in Hierarchical Key Assignment Schemes for Dynamic Structures, A Compact Representation for Syntactic Dependencies in QBFs, Multi-instance learning of pretopological spaces to model complex propagation phenomena: application to lexical taxonomy learning, Transitive closure and transitive reduction in bidirected graphs, ``Global graph problems tend to be intractable, Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations, Maximal independent sets in caterpillar graphs, Component-graph construction, LP structures on type lattices and some refactoring problems, Alarm placement in systems with fault propagation, Resource allocation by means of project networks: Dominance results, An improved transitive closure algorithm, Polyhedral Aspects of Stable Marriage, Exploiting causality in gene network reconstruction based on graph embedding, A faster tree-decomposition based algorithm for counting linear extensions, Acyclic Digraphs, Combinatorial Representation of Parameter Space for Switching Networks, Biclique graphs of split graphs, Transitive reduction of a rectangular Boolean matrix, Transitive reduction of a nilpotent Boolean matrix, Generic flux coupling analysis, Approximating Minimum Representations of Key Horn Functions, Optimal constructions of reversible digraphs, An incremental algorithm for DLO quantifier elimination via constraint propagation