- Finding Minimal Clusters in st-DAGs
2026/03/27 by Ulrich Vogl, Markus Siegle · 1 voice
Computer Science · #Advanced Graph Theory Research #Cluster (spacecraft) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Digraph #Directed graph #Exponential function #Point (geometry) #Quadratic equation #Synchronizing #Vertex (graph theory) #cs.DM
- The Directed Grid Theorem
2014/11/20 by Ken-ichi Kawarabayashi, Ken‐ichi Kawarabayashi, Kawarabayashi, Ken-ichi +2 · 7 citations
Computer Science · Mathematics · #05C20 #05C83 #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Conjecture #Digraph #Directed graph #Discrete Mathematics (cs.DM) #Discrete mathematics #Disjoint sets #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Graph minor #Graph theory #Line graph #Mathematics #Pathwidth #Pigeonhole principle #Robertson–Seymour theorem #Voltage graph #cs.DM #math.CO #msc:05C20 #msc:05C83
- Causal Networks: Semantics and Expressiveness
2013/03/27 by Tom S. Verma, Verma, Tom S., Judea Pearl +1 · 106 citations
Computer Science · Decision Sciences · Mathematics · #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Axiom #Bayesian Modeling and Causal Inference #Computer science #Conditional independence #Data Quality and Management #Data mining #Dependency (UML) #Dependency theory (database theory) #Directed acyclic graph #Directed graph #FOS: Computer and information sciences #Functional dependency #Graph #Graphical model #Logic, Reasoning, and Knowledge #Mathematics #Probabilistic logic #Programming language #Relational database #Semantics (computer science) #Theoretical computer science #Undirected graph #cs.AI
- Path Laplacian matrices: Introduction and application to the analysis of consensus in networks
2011/12/23 by Ernesto Estrada · 65 citations
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Algebraic connectivity #Combinatorics #Complex Network Analysis Techniques #Computer science #Directed graph #Discrete mathematics #Distance matrix #Eigenvalues and eigenvectors #Gene Regulatory Network Analysis #Graph #Graph theory and applications #Laplace operator #Laplacian matrix #Line graph #Markov chain #Mathematics #Path (computing) #Resistance distance #Shortest path problem
- Shortest paths in directed planar graphs with negative lengths
2010/03/01 by Philip N. Klein, Shay Mozes, Oren Weimann · 92 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Planar graph #Combinatorics #Directed graph #Planar #Mathematics #Directed acyclic graph #Feedback arc set #Node (physics) #Arc (geometry) #Graph #Discrete mathematics #Space (punctuation) #Computer science #Line graph #Geometry #Physics
- A fixed-parameter algorithm for the directed feedback vertex set problem
2008/10/01 by Jianer Chen, Yang Liu, Songjian Lu +2 · 297 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #semigroups and automata theory #Parameterized complexity #Feedback vertex set #Vertex (graph theory) #Feedback arc set #Vertex cover #Mathematics #Combinatorics #Set (abstract data type) #Directed graph #Computation #Algorithm #Graph #Discrete mathematics #Computer science #Line graph
- Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
2004/09/01 by R. Olfati-Saber, Reza Olfati‐Saber, Richard M. Murray +1 · 12,780 citations
Computer Science · Mathematics · #Algebraic connectivity #Algebraic graph theory #Algorithm #Artificial intelligence #Computer science #Consensus #Convergence (economics) #Directed graph #Distributed Control Multi-Agent Systems #Function (biology) #Graph #Graph theory #Laplacian matrix #Lyapunov function #Mathematics #Multi-agent system #Network topology #Neural Networks Stability and Synchronization #Opportunistic and Delay-Tolerant Networks #Theoretical computer science #Topology (electrical circuits) #Uniform consensus
- Testing subgraphs in directed graphs
2004/06/09 by Noga Alon, A. Shapira, Asaf Shapira · 78 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Characterization (materials science) #Combinatorics #Complexity and Algorithms in Graphs #Directed graph #Discrete mathematics #Function (biology) #Graph #Lemma (botany) #Mathematics #Optimization and Search Problems #Polynomial #Property (philosophy) #Property testing
- Directed Tree-Width
2001/05/01 by Thor Johnson, Neil Robertson, P.D. Seymour +2 · 192 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Digraph #Directed graph #Discrete mathematics #Graph #Interconnection Networks and Systems #Mathematics #Tree (set theory)
- A model for the emergence of cooperation, interdependence, and structure in evolving networks
2000/05/18 by Sanjay Jain, Sandeep Krishna · 213 citations
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · Social Sciences · #Algorithm #Artificial intelligence #Autocatalysis #Biological network #Biology #Catalysis #Complex network #Computational biology #Computer science #Directed graph #Epistemology #Evolutionary Game Theory and Cooperation #Evolutionary biology #Graph #Network formation #Network model #Origins and Evolution of Life #Physics #Protein Structure and Dynamics #Set (abstract data type) #Simple (philosophy) #Statistical physics #Theoretical computer science #cond-mat #nlin.AO
- A Faster Deterministic Maximum Flow Algorithm
1994/11/01 by Valerie King, V. King, S. Rao +3 · 115 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Constant (computer programming) #Control flow graph #Deterministic algorithm #Dijkstra's algorithm #Directed graph #Discrete mathematics #Flow (mathematics) #Freivalds' algorithm #Game Theory and Voting Systems #Graph #Mathematics #Maximum flow problem #Randomized algorithm #Running time #Shortest path problem #Time complexity
- A fast and effective heuristic for the feedback arc set problem
1993/10/01 by Peter Eades, Xuemin Lin, W.F. Smyth · 202 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Digraph #Directed graph #Discrete mathematics #Feedback arc set #Graph #Heuristic #Interconnection Networks and Systems #Line graph #Mathematical optimization #Mathematics
- Graph drawing by force‐directed placement
1991/11/01 by Thomas M. J. Fruchterman, Edward M. Reingold · 6,404 citations
Computer Science · Mathematics · #Algorithm #Analogy #Artificial intelligence #Computer science #Data Visualization and Analytics #Directed graph #Enhanced Data Rates for GSM Evolution #Graph #Graph drawing #Heuristic #Mathematics #Simple (philosophy) #Software Engineering Research #Theoretical computer science #Topological and Geometric Data Analysis #Undirected graph
- A New Algorithm for Computing the Maximal Closure of a Graph
1990/03/01 by Bruce Faaland, Kiseog Kim, Tom Schmitt · 17 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Computational Geometry and Mesh Generation #Closure (psychology) #Closure problem #Mathematics #Maximum flow problem #Algorithm #Directed graph #Graph #Minimum cut #Node (physics) #Combinatorics #Discrete mathematics
- How to compute the Wiener index of a graph
1988/07/01 by Bojan Mohar, Tomaž Pisanski · 86 citations
Chemistry · Computer Science · Mathematics · #Combinatorics #Computational Drug Discovery Methods #Computer science #Connectivity #Directed graph #Graph #Graph theory and applications #History and advancements in chemistry #Index (typography) #Mathematical chemistry #Mathematics #Topological index #Wiener index
- A labeling algorithm to recognize a line digraph and output its root graph
1982/08/01 by Maciej M. Syslo, Maciej M. Sysło · 36 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Computer science #Digraph #Directed graph #Graph #Graph Labeling and Dimension Problems #Line (geometry) #Line graph #Mathematics #graph theory and CDMA systems
- The road-colouring problem
1981/03/01 by G. L. O’Brien · 58 citations
Business, Management and Accounting · Computer Science · Mathematics · #Optics and Image Analysis #Graph Labeling and Dimension Problems #Aperiodic graph #Mathematics #Combinatorics #Vertex (graph theory) #Constant (computer programming) #Prime (order theory) #Graph #Finite graph #Directed graph #Discrete mathematics #Computer science
- Efficient determination of the transitive closure of a directed graph
1971/01/01 by Ian Munro · 120 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Closure (psychology) #Combinatorics #Computer science #Directed graph #Graph #Interconnection Networks and Systems #Line graph #Mathematics #Theoretical computer science #Transitive closure #Transitive reduction #Transitive relation #Voltage graph #graph theory and CDMA systems
- A transitive closure algorithm
1970/03/01 by Paul W. Purdom, Paul Purdom · 81 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Binary logarithm #Closure (psychology) #Combinatorics #Complexity and Algorithms in Graphs #Dijkstra's algorithm #Directed graph #Discrete mathematics #Floyd–Warshall algorithm #Graph #Line graph #Mathematics #Shortest path problem #Time complexity #Transitive closure #Transitive reduction #Transitive relation #Undirected graph #Voltage graph
- Topological sorting of large networks
1962/11/01 by Arthur B. Kahn · 747 citations
Computer Science · Engineering · Mathematics · #Embedded Systems Design Techniques #Manufacturing Process and Optimization #Petri Nets in System Modeling #Sorting #Topological sorting #Computer science #Sorting network #Sorting algorithm #Topology (electrical circuits) #Algorithm #Mathematics #Combinatorics #Directed graph