Augmenting weighted graphs to establish directed point-to-point connectivity
From MaRDI portal
Publication:2359805
DOI10.1007/s10878-016-0023-yzbMath1372.90111OpenAlexW2346528079MaRDI QIDQ2359805
Mehdy Roayaei, Mohammadreza Razzazi
Publication date: 22 June 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-016-0023-y
graph augmentationfixed-parameter tractabilityparameterized algorithmdirected Steiner networkpoint-to-point connectivity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation for orienting mixed graphs
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- On the point-to-point connection problem
- Improved approximability and non-approximability results for graph diameter decreasing problems
- The bridge-connectivity augmentation problem with a partition constraint
- Edge-connectivity augmentation problems
- The point-to-point delivery and connection problems: Complexity and algorithms
- A unifying augmentation algorithm for two-edge connectivity and biconnectivity
- The point-to-point connection problem - analysis and algorithms
- Fixed-parameter tractability of disjunction-free default reasoning
- Incrementing bipartite digraph edge-connectivity
- Independence free graphs and vertex connectivity augmentation
- A note on finding the bridges of a graph
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Optimal orientations of graphs and digraphs: A survey
- On cyclic vertex-connectivity of Cartesian product digraphs
- Approximation algorithms and hardness results for labeled connectivity problems
- Digraph width measures in parameterized algorithmics
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Design networks with bounded pairwise distance
- Fixed-Parameter and Approximation Algorithms: A New Look
- Kernelization and complexity results for connectivity augmentation problems
- Augmenting Undirected Node-Connectivity by One
- Finding a Smallest Augmentation to Biconnect a Graph
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Minimizing the Diameter of a Network Using Shortcut Edges
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Approximating Node-Connectivity Augmentation Problems
- Graph minors. II. Algorithmic aspects of tree-width
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Practical algorithms on partial k-trees with an application to domination-like problems
- Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics
- Fibonacci heaps and their uses in improved network optimization algorithms
- Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
- Fundamentals of Computation Theory
- The steiner problem in graphs
- Depth-First Search and Linear Graph Algorithms
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
This page was built for publication: Augmenting weighted graphs to establish directed point-to-point connectivity
