The complexity of finding maximum disjoint paths with length constraints
From MaRDI portal
Publication:4741713
DOI10.1002/net.3230120306zbMath0504.68041OpenAlexW2000733920MaRDI QIDQ4741713
Alon Itai, Yehoshua Perl, Yossi Shiloach
Publication date: 1982
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230120306
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (47)
Length-bounded disjoint paths in planar graphs ⋮ OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks ⋮ New algorithms for pattern matching with wildcards and length constraints ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ Finding disjoint paths with related path costs ⋮ On the hop-constrained survivable network design problem with reliable edges ⋮ Lower bounds on two-terminal network reliability ⋮ On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks ⋮ Large fault-tolerant interconnection networks ⋮ Hop‐level flow formulation for the survivable network design with hop constraints problem ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks ⋮ Finding paths with minimum shared edges ⋮ The disjoint shortest paths problem ⋮ Pattern matching with wildcards and length constraints using maximum network flow ⋮ Complexity of the traveling tournament problem ⋮ On b-acyclic chromatic number of a graph ⋮ Edge degeneracy: algorithmic and structural results ⋮ The Menger number of the Cartesian product of graphs ⋮ Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty ⋮ On shortest disjoint paths in planar graphs ⋮ On the maximum disjoint paths problem on edge-colored graphs ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Fractals for Kernelization Lower Bounds ⋮ Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ An efficient algorithm for testing goal-minimality of graphs ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Balanced paths in acyclic networks: Tractable cases and related approaches ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ The complexity of finding two disjoint paths with min-max objective function ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Walking through waypoints ⋮ Models for optimal survivable routing with a minimum number of hops: comparing disaggregated with aggregated models ⋮ Finding the most vital arcs in a network ⋮ On s-t paths and trails in edge-colored graphs ⋮ Searching for a Visible, Lazy Fugitive ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Counterexamples to theorems of Menger type for the diameter ⋮ Self-spanner graphs ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut ⋮ Length-constrained path-matchings in graphs
This page was built for publication: The complexity of finding maximum disjoint paths with length constraints
