Shortcutting directed and undirected networks with a degree constraint
DOI10.1016/J.DAM.2016.12.016zbMATH Open1355.05235OpenAlexW2576776590MaRDI QIDQ507583FDOQ507583
Authors: Richard B. Tan, Erik Jan van Leeuwen, J. 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
Recommendations
networksDAGsdiameterNP-hardnesscompressionstability number\(W[2\)-hardness]feedback dimensionpath coversrooted directed treesshortcutting
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Paths and cycles (05C38)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Succinct ordinal trees with level-ancestor queries
- Efficiency of a Good But Not Linear Set Union Algorithm
- Partitioning 2-edge-colored graphs by monochromatic paths and cycles
- Diameter bounds for altered graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The diameter of randomly perturbed digraphs and some applications
- Diameter increase caused by edge deletion
- Title not available (Why is that?)
- Computing on a free tree via complexity-preserving mappings
- Parallel Shortcutting of Rooted Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Shortcutting Planar Digraphs
- Transitive-closure spanners: a survey
- Design networks with bounded pairwise distance
- A Uniform Approach Towards Succinct Representation of Trees
- Testing the diameter of graphs
- The parametric complexity of graph diameter augmentation
- Minimizing the diameter of a network using shortcut edges
- Decreasing the diameter of bounded degree graphs
- Augmenting graphs to minimize the diameter
- Improved approximability and non-approximability results for graph diameter decreasing problems
- Variations on the Gallai-Milgram theorem
- Every finite strongly connected digraph of stability 2 has a Hamiltonian path
- An algorithmic note on the gallai-milgram theorem
- The shortcut problem - complexity and algorithms
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- The Serial Transitive Closure Problem for Trees
- Structure of polynomial-time approximation
- Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture
Cited In (5)
- Minimizing the diameter of a network using shortcut edges
- The shortcut problem - complexity and algorithms
- On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Title not available (Why is that?)
This page was built for publication: Shortcutting directed and undirected networks with a degree constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507583)
