The directed subgraph homeomorphism problem
From MaRDI portal
Publication:1132111
DOI10.1016/0304-3975(80)90009-2zbMath0419.05028OpenAlexW2569646339MaRDI QIDQ1132111
James Wyllie, Steven Fortune, John E. Hopcrofts
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90009-2
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)
Related Items
Strong Lower Bounds for a Survivable Network Design Problem, Edge-Disjoint Branchings in Temporal Graphs, Faster 2-Disjoint-Shortest-Paths Algorithm, Complexity of column generation in network design with path-based survivability mechanisms, Recoverable robust shortest path problems, The complexity of welfare maximization in congestion games, Hardness and approximation results for packing Steiner trees, Towards the Graph Minor Theorems for Directed Graphs, Searching forK3,3in linear time, Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs, On the Pathwidth of Almost Semicomplete Digraphs, Paths and trails in edge-colored graphs, Polynomial time algorithms for tracking path problems, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, Free multiflows in bidirected and skew-symmetric graphs, The maximum integer multiterminal flow problem in directed graphs, Redundancy in logic. II: 2CNF and Horn propositional formulae, Arc-Disjoint Paths in Decomposable Digraphs, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Maximum Throughput Network Routing Subject to Fair Flow Allocation, Simple paths with exact and forbidden lengths, On packing time-respecting arborescences, Finding a path with two labels forbidden in group-labeled graphs, Packing arc-disjoint cycles in tournaments, Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, On the 2‐cyclic property in 2‐regular digraphs, Simple undirected two-commodity integral flow with a unitary demand, Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results, Evaluation and Enumeration Problems for Regular Path Queries, On the parameterized complexity of the connected flow and many visits TSP problem, Linearizable special cases of the quadratic shortest path problem, Graph planning with expected finite horizon, A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints, Adapting the Directed Grid Theorem into an FPT Algorithm, The Induced Disjoint Paths Problem, A recommender system for train routing: when concatenating two minimum length paths is not the minimum length path, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, On the problem of finding disjoint cycles and dicycles in a digraph, Unnamed Item, A tight lower bound for edge-disjoint paths on planar DAGs, Multiflow Feasibility: An Annotated Tableau, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, (Arc-)disjoint flows in networks, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Digraph width measures in parameterized algorithmics, On the edge capacitated Steiner tree problem, On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas, Finding k Partially Disjoint Paths in a Directed Planar Graph, Linkedness and Ordered Cycles in Digraphs, Cost-based filtering for shorter path constraints, On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms, Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs, Edge-disjoint branchings in temporal digraphs, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, How much can taxes help selfish routing?, Meet and merge: approximation algorithms for confluent flows, Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles, On the severity of Braess's paradox: designing networks for selfish users is hard, Half-integral linkages in highly connected directed graphs, Disjoint paths in graphs. (Reprint), Routing with congestion in acyclic digraphs, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, Unnamed Item, Achieving target equilibria in network routing games without knowing the latency functions, On the computational complexity of combinatorial flexibility problems, Two disjoint shortest paths problem with non-negative edge length, The undirected two disjoint shortest paths problem, The complexity of computing a robust flow, DAG-Width and Circumference of Digraphs, Complexity of a classical flow restoration problem, Theoretical and computational advances for network diversion, On the complexity of algorithms for detecting \(k\)-length negative cost cycles, The directed 2-linkage problem with length constraints, A relaxation of the directed disjoint paths problem: a global congestion metric helps, A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps., An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs, Packing Arc-Disjoint Cycles in Tournaments, A Slice Theoretic Approach for Embedding Problems on Digraphs, On width measures and topological problems on semi-complete digraphs, SWITCHING GRAPHS, Arc-Disjoint Directed and Undirected Cycles in Digraphs, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, On Digraph Width Measures in Parameterized Algorithmics, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, The Directed Disjoint Shortest Paths Problem, Ordered optimal solutions and parametric minimum cut problems, Basic Terminology, Notation and Results, Tournaments and Semicomplete Digraphs, Acyclic Digraphs, Euler Digraphs, Planar Digraphs, Quasi-Transitive Digraphs and Their Extensions, Digraphs of Bounded Width, Lexicographic Orientation Algorithms, Disjoint sub(di)graphs in digraphs, Backdoors to tractable answer set programming, The complexity of multi-mean-payoff and multi-energy games, Disjoint Paths—A Survey, Steiner Problems with Limited Number of Branching Nodes, Safety in \(s\)-\(t\) paths, trails and walks, Algorithms for finding disjoint path covers in unit interval graphs, Chordless paths through three vertices, Cycles through \(k\) vertices in bipartite tournaments, Minimum \(k\) arborescences with bandwidth constraints, Even cycles in directed graphs, Characterization of even directed graphs, Computing strictly-second shortest paths, On parameterized complexity of liquid democracy, The complexity of minimal satisfiability problems, Congestion games with mixed objectives, On digraphs with no two disjoint directed cycles, The complexity of induced minors and related problems, The label cut problem with respect to path length and label frequency, Finding disjoint paths with related path costs, Edge-disjoint in- and out-branchings in tournaments and related path problems, MNP: A class of NP optimization problems, Disjoint cycles in digraphs, Expressiveness and complexity of graph logic, Packing directed circuits, Bounded arity Datalog \((\neq)\) queries on graphs, On orientations and shortest paths, Some recent progress and applications in graph minor theory, Computing pure Nash and strong equilibria in bottleneck congestion games, Quantifying the extent of lateral gene transfer required to avert a `genome of Eden', On the hardness of network design for bottleneck routing games, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Inefficiencies in network models: a graph-theoretic perspective, The disjoint shortest paths problem, The subgraph homeomorphism problem, Vertex-disjoint directed and undirected cycles in general digraphs, Are there any good digraph width measures?, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, The Rabin index of parity games: its complexity and approximation, Finding and fixing faults, On making directed graphs transitive, Synthesizing bounded-time 2-phase fault recovery, Disjoint paths in graphs, 2-linked graphs, On the complexity of the edge-disjoint min-min problem in planar digraphs, On shortest disjoint paths in planar graphs, Optimizing end-to-end performance of data-intensive computing pipelines in heterogeneous network environments, Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, A simple solution to the two paths problem in planar graphs, 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, Symmetric space-bounded computation, Disjoint paths in unions of tournaments, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Edge-disjoint paths in digraphs with bounded independence number, Criticality for multicommodity flows, Protection of flows under targeted attacks, Finding a subdivision of a digraph, Computing solutions of the multiclass network equilibrium problem with affine cost functions, Disjoint paths in tournaments, Directed circuits on a torus, Highly connected non-2-linked digraphs, Parameterized algorithms for list \(K\)-cycle, Finding supported paths in heterogeneous networks, Finding temporal paths under waiting time constraints, A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs, Network topology and equilibrium existence in weighted network congestion games, Optimal parallel algorithms for path problems on planar graphs, Forbidden directed minors and Kelly-width, Special cases of the quadratic shortest path problem, Network characterizations for excluding Braess's paradox, The \(k\)-path tree matroid and its applications to survivable network design, Finding read-once resolution refutations in systems of 2CNF clauses, Detecting cycles through three fixed vertices in a graph, On the structure of locally semicomplete digraphs, On the approximability of robust network design, Links in edge-colored graphs, Induced disjoint paths problem in a planar digraph, Minimal multicut and maximal integer multiflow: a survey, Multiflows in symmetric digraphs, The complexity of finding two disjoint paths with min-max objective function, Exact localisations of feedback sets, Robust flows over time: models and complexity results, Disjoint paths in symmetric digraphs, Tournament pathwidth and topological containment, A minimization version of a directed subgraph homeomorphism problem, On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs, Branch-and-price-and-cut algorithms for solving the reliable \(h\)-paths problem, Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem, Cycles and paths in bipartite tournaments with spanning configurations, Tournament immersion and cutwidth, Structure and recognition of graphs with no 6-wheel subdivision, Disjoint directed and undirected paths and cycles in digraphs, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, On the complexity of solving a decision problem with flow-depending costs: the case of the IJsselmeer dikes, Hereditarily hard \(H\)-colouring problems, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Alternating paths in edge-colored complete graphs, Directed tree-width, Signsolvability revisited, The 2-linkage problem for acyclic digraphs, The complexity of counting homeomorphs, An approach to the subgraph homeomorphism problem, Fixed-parameter complexity in AI and nonmonotonic reasoning, Sign-nonsingular matrices and even cycles in directed graphs, Parameterizing path partitions, Combinatorial acyclicity models for potential‐based flows, Solving the edge‐disjoint paths problem using a two‐stage method, A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem, Cut-sufficient directed 2-commodity multiflow topologies, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, Directed Steiner tree packing and directed tree connectivity, Detours in directed graphs, Financial interbanking networks resilience under shocks propagation, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths, An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization, A Trichotomy for Regular Trail Queries, Reconfiguration of time-respecting arborescences, Almost disjoint paths and separating by forbidden pairs, Unnamed Item, Finding an induced subdivision of a digraph, Connectivity and inference problems for temporal networks, Finding Temporal Paths Under Waiting Time Constraints., Efficient algorithms for measuring the funnel-likeness of DAGs, Inserting an edge into a geometric embedding, A note on orientations of mixed graphs, Inserting an edge into a geometric embedding, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Infinitary logic for computer science, Computing the rooted triplet distance between phylogenetic networks, Paths and Trails in Edge-Colored Graphs, Cycle-connected mixed graphs and related problems, Cycle-connected mixed graphs and related problems, Walking through waypoints, Parameterized algorithms for generalizations of directed feedback vertex set, On Mergings in Acyclic Directed Graphs, Computing the 2-blocks of directed graphs, Measuring and Synthesizing Systems in Probabilistic Environments, A logarithmic approximation for unsplittable flow on line graphs, Unnamed Item, Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems, Disjoint Paths in Decomposable Digraphs
Cites Work
