Shortcutting directed and undirected networks with a degree constraint
From MaRDI portal
Publication:507583
DOI10.1016/j.dam.2016.12.016zbMath1355.05235OpenAlexW2576776590MaRDI QIDQ507583
Richard B. Tan, Jan van Leeuwen, Erik Jan van Leeuwen
Publication date: 6 February 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/350789
networksdiameterstability numbercompressionNP-hardnessDAGs\(W[2\)-hardness]feedback dimensionpath coversrooted directed treesshortcutting
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Partitioning 2-edge-colored graphs by monochromatic paths and cycles
- Augmenting graphs to minimize the diameter
- Structure of polynomial-time approximation
- Improved approximability and non-approximability results for graph diameter decreasing problems
- Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture
- Computing on a free tree via complexity-preserving mappings
- Variations on the Gallai-Milgram theorem
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Every finite strongly connected digraph of stability 2 has a Hamiltonian path
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The parametric complexity of graph diameter augmentation
- Design networks with bounded pairwise distance
- Succinct ordinal trees with level-ancestor queries
- An algorithmic note on the gallai-milgram theorem
- Parallel Shortcutting of Rooted Trees
- The Shortcut Problem - Complexity and Algorithms
- A Uniform Approach Towards Succinct Representation of Trees
- Minimizing the Diameter of a Network Using Shortcut Edges
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Diameter increase caused by edge deletion
- Efficiency of a Good But Not Linear Set Union Algorithm
- The Serial Transitive Closure Problem for Trees
- Decreasing the diameter of bounded degree graphs
- Testing the diameter of graphs
- Shortcutting Planar Digraphs
- Transitive-Closure Spanners: A Survey
- Diameter bounds for altered graphs
- The diameter of randomly perturbed digraphs and some applications
