Augmenting weighted graphs to establish directed point-to-point connectivity

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

zbMATH Keywords

graph augmentationfixed-parameter tractabilityparameterized algorithmdirected Steiner networkpoint-to-point connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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