An Algorithm for Finding a Minimum Equivalent Graph of a Digraph

No abstract is available for this paper.

• Publication year

  1969

• Venue

  Journal of the ACM

• Publication date

  1969-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/321526.321534
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Structural Models: An Introduction to the Theory of Directed Graphs.

  1966cited by this paper
• Structural Models: An Introduction to the Theory of Directed Graphs

  1965cited by this paper
• A Theorem on Boolean Matrices

  1962cited by this paper
• Algorithm 96: Ancestor

  1962cited by this paper

• From data to concepts via wiring diagrams

  2025cites this paper
• Core stability and strategy-proofness in hedonic coalition formation problems with friend-oriented preferences

  2025cites this paper
• A structured framework for supporting the participatory development of consensual scenario narratives

  2025cites this paper
• Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability Solving

  2024cites this paper
• Directed Transit Functions

  2024cites this paper
• Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis

  2023cites this paper
• Fuzzy rough digraph based on strength of connectedness with application

  2023cites this paper
• Taming transitive redundancy for context-free language reachability

  2022cites this paper
• LazyB: fast and cheap genome assembly

  2021cites this paper
• Self-Adjusting Packet Classification

  2021influential citation
• An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph

  2020cites this paper
• HcRPC: Highly Compact Reachability Preserving Graph Compression With Corrections

  2019cites this paper
• The Role of Structural Reasoning in the Genesis of Graph Theory

  2019influential citation
• Parameterized Algorithms for Survivable Network Design with Uniform Demands

  2018influential citation
• Vectorial Problem on Combinations on Hypergraphs

  2018cites this paper
• World's Best Universities and Personalized Rankings

  2018cites this paper
• Moving space target detection algorithm based on trajectory similarity

  2018cites this paper
• Mining human mobility patterns from pervasive spatial and temporal data

  2018cites this paper
• Using Multiple Fidelity Models in Motion Planning

  2018cites this paper
• Fast Exact Algorithms for Survivable Network Design with Uniform Requirements

  2017cites this paper
• Path-Contractions, Edge Deletions and Connectivity Preservation

  2017cites this paper
• Plan-Time Multi-Model Switching for Motion Planning

  2017cites this paper
• On finding highly connected spanning subgraphs

  2017influential citation
• Minimal equivalent subgraphs containing a given set of arcs

  2017cites this paper
• Shrink: Distance preserving graph compression

  2017cites this paper
• Performance Optimization Techniques and Tools for Distributed Graph Processing

  2016cites this paper
• Reconfigurable Battery Techniques and Systems: A Survey

  2016cites this paper
• Topology-based image segmentation using LBP pyramids

  2016cites this paper
• The shortest path is not always a straight line

  2016cites this paper
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms

  2016cites this paper
• iRE: An Interactive Requirements Engineering Framework

  2016cites this paper
• Minimum equivalent precedence relation systems

  2015cites this paper
• Maximal and Maximum Transitive Relation Contained in a Given Binary Relation

  2015cites this paper
• The Adversarial Noise Threshold for Distributed Protocols

  2014cites this paper
• On Layered Drawings of Planar Graphs

  2014cites this paper
• Metabolic Networks, Thermodynamic Constraints, and Matroid Theory (Metabolische Netzwerke, Thermodynamische Nebenbedingungen und Matroidtheorie)

  2014cites this paper
• Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks

  2013cites this paper
• Mining Declarative Models Using Time Intervals

  2013cites this paper
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

  2013influential citation
• Query preserving graph compression

  2012cites this paper
• Compact Representation of Posets

  2011cites this paper
• A proof of the DBRF-MEGN method, an algorithm for deducing minimum equivalent gene networks

  2011cites this paper
• A method for optimizing communication paths in distributed systems

  2011cites this paper
• A Connectivity Reduction Strategy for Multi-agent Systems

  2010cites this paper
• Property-aware program sampling

  2010cites this paper
• Parallel algorithms for transitive reduction for weighted graphs

  2010cites this paper
• Monitoring software using property-aware program sampling

  2010influential citation
• Approximating Transitive Reductions for Directed Networks

  2009cites this paper
• The integrality gap of the asymmetric travelling salesman problem

  2008cites this paper
• Approximating Transitivity in Directed Networks

  2008cites this paper
• Digraph decompositions and monotonicity in digraph searching

  2008cites this paper
• The Steiner Equivalent Subgraph Polyhedra for Series-Parallel Digraphs

  2005cites this paper
• Studying Graph Connectivity

  2002cites this paper
• Approximating the minimum strongly connected subgraph via a matching lower bound

  2001influential citation
• TRANSITIVE REDUCTION OF A HLPOTENT

  2001cites this paper
• The Directed Steiner Network problem is tractable for a constant number of terminals

  1999cites this paper
• Efficient coverage testing using global dominator graphs

  1999cites this paper
• Approximation algorithms for finding highly connected subgraphs

  1996cites this paper
• On Strongly Connected Digraphs with Bounded Cycle Length

  1996cites this paper
• Approximating the minimum equivalent digraph

  1994cites this paper
• Dominators, super blocks, and program coverage

  1994cites this paper
• STRUCTURAL REPRESENTATIONS OF SCHUR COMPLEMENTS IN SPARSE MATRICES

  1993cites this paper
• Graph-theoretic techniques for computer intraconnection minimization

  1993cites this paper
• Finding a Minimal Transitive Reduction in a Strongly Connected Digraph within Linear Time

  1989cites this paper
• Rationale and Methods for Abductice Reasoning in Natural-Language Interpretation

  1989cites this paper
• On Minimum Flow and Transitive Reduction

  1988cites this paper
• Parsing a graph-grammar

  1988cites this paper
• An efficiently solvable case of the minimum weight equivalent subgraph problem

  1985cites this paper
• Transitive reduction of a rectangular boolean matrix

  1984cites this paper
• Transitive reduction of a nilpotent boolean matrix

  1984cites this paper
• Finding a minimum equivalent graph of a digraph

  1982cites this paper
• Reduction of a nilpotent fuzzy matrix

  1982cites this paper
• Methods for Checking the Consistency of Precedence Constraints

  1980cites this paper
• Graph Algorithms for the Synthesis and Manipulation of Data Base Schemes

  1980cites this paper
• An algorithm for finding a minimal equivalent graph of a strongly connected digraph

  1979influential citation
• A Correction to a Unilaterally Connected Components Algorithm

  1978cites this paper
• An Efficient Algorithm for Constructing Hierarchical Graphs

  1976cites this paper
• An Algorithm for Finding a Minimal Equivalent Graph of a Digraph

  1975cites this paper
• Computationally Related Problems

  1974cites this paper
• Transitively equivalent directed graphs

  1973cites this paper
• Some Related Problems from Network Flows, Game Theory and Integer Programming

  1972cites this paper