Network Flow and Testing Graph Connectivity
From MaRDI portal
Publication:4094634
DOI10.1137/0204043zbMath0328.90031OpenAlexW2008292658WikidataQ56562705 ScholiaQ56562705MaRDI QIDQ4094634
Shimon Even, Robert Endre Tarjan
Publication date: 1975
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0204043
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)
Related Items
Blocking trails for \(f\)-factors of multigraphs, A weight-scaling algorithm for \(f\)-factors of multigraphs, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Uniformly connected graphs, Maximum skew-symmetric flows, Output-sensitive reporting of disjoint paths (extended abstract), Orthogonal layout with optimal face complexity, Scaling algorithms for network problems, Explaining robust additive utility models by sequences of preference swaps, Minimum cuts in geometric intersection graphs, Finding a complete matching with the maximum product on weighted bipartite graphs, A faster parallel algorithm for \(k\)-connectivity, Finding hidden independent sets in interval graphs, On computing minimum\((s,t)\)-cuts in digraphs, On Element-Connectivity Preserving Graph Simplification, Recent developments in maximum flow algorithms, On the complexity of the maximum satisfiability problem for Horn formulas, Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations, Iteratively reweighted least squares and slime mold dynamics: connection and convergence, A random NC algorithm for depth first search, What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs, Unit Capacity Maxflow in Almost $m^{4/3}$ Time, On the efficiency of maximum-flow algorithms on networks with small integer capacities, Maximum 0-1 timed matching on temporal graphs, Incremental assignment problem, Acyclic k-connected subgraphs for distributed alternate routing in communications networks, Ranking intervals under visibility constraints∗, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Scheduling unit-time jobs on processors with different capabilities, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Hypergraph Cuts with General Splitting Functions, Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs, Systems of distinct representatives for k families of sets, Efficient algorithm for the vertex connectivity of trapezoid graphs, The subgraph homeomorphism problem, Pattern matching with wildcards and length constraints using maximum network flow, A polynomial algorithm determining cyclic vertex connectivity of \(k\)-regular graphs with fixed \(k\), A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs, Minimum-cost flows in unit-capacity networks, On flows in simple bidirected and skew-symmetric networks, On b-acyclic chromatic number of a graph, Game connectivity of graphs, Approximating the treewidth of AT-free graphs., On the theoretical efficiency of various network flow algorithms, Path-contractions, edge deletions and connectivity preservation, A probabilistic algorithm for vertex connectivity of graphs, Graph connectivity, partial words, and a theorem of Fine and Wilf, A simple variant of node connectivity is NP-complete, Same stats, different graphs (graph statistics and why we need graph drawings), The General Minimum Fill-In Problem, Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs, A graph-theoretic characterization for the rank of the transfer matrix of structured system, An algorithm for finding all thek-components of a digraph, An efficient algorithm to solve connectivity problem on trapezoid graphs, Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing, A Constructive Arboricity Approximation Scheme, Partition-based logical reasoning for first-order and propositional theories, A model for minimizing active processor time, Network reliability in Hamiltonian graphs, Forests, frames, and games: Algorithms for matroid sums and applications, A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph, Algorithmic aspects of homophyly of networks, New scaling algorithms for the assignment and minimum mean cycle problems, Approximating minimum cuts under insertions, A linear time algorithm for computing 3-edge-connected components in a multigraph, On orienting graphs for connectivity: Projective planes and Halin graphs, Unnamed Item, Graph invariants and large cycles: a survey, A good algorithm for lexicographically optimal flows in multi-terminal networks, Maximum bipartite flow in networks with adaptive channel width, A simple criterion for structurally fixed modes, Bottleneck flows in unit capacity networks, A combinatorial algorithm for weighted stable sets in bipartite graphs, Algorithms for core stability, core largeness, exactness, and extendability of flow games, Unnamed Item, Unnamed Item, Computing vertex-disjoint paths in large graphs using MAOs, Faster Algorithms for Semi-Matching Problems, An \(O(IVI^3)\) algorithm for finding maximum flows in networks, Validity of clusters formed by graph-theoretic cluster methods, Edge-disjoint branching in directed multigraphs, Cycle-connected mixed graphs and related problems, Cycle-connected mixed graphs and related problems, Min-Cost Flow in Unit-Capacity Planar Graphs, Extracting maximal information about sets of minimum cuts, INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, A polynomial time algorithm for cyclic vertex connectivity of cubic graphs, Depth First Search in the Semi-streaming Model, Parallel algorithm to find maximum capacity paths, Finding triconnected components of graphs, Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs, Bounds on the Reliability Polynomial for Shellable Independence Systems, The clique-perfectness and clique-coloring of outer-planar graphs, CONNECTIVITY PROPERTIES IN RANDOM REGULAR GRAPHS WITH EDGE FAULTS, Fast Augmenting Paths by Random Sampling from Residual Graphs, GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE, An improved algorithm for decomposing arc flows into multipath flows, Depth-first search is inherently sequential, An approach to the subgraph homeomorphism problem, Computing maximum non-crossing matching in convex bipartite graphs, Tree-core and tree-coritivity of graphs, Improved algorithms for graph four-connectivity, Minimum cost source location problem with vertex-connectivity requirements in digraphs, On the complexity of the vector connectivity problem
Uses Software
