Shortcutting directed and undirected networks with a degree constraint

DOI10.1016/J.DAM.2016.12.016MaRDI QIDQ507583zbMATHOpenAlexFDO

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

zbMATH Keywords

networksDAGsdiameterNP-hardnesscompressionstability number\(W[2\)-hardness]feedback dimensionpath coversrooted directed treesshortcutting

Mathematics Subject Classification ID

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)

Recommendations

• Minimizing the diameter of a network using shortcut edges
• scientific article; zbMATH DE number 2079397
• Shortcut sets for plane Euclidean networks (extended abstract)
• Shortcut sets for the locus of plane Euclidean networks
• Shortcutting Planar Digraphs

Cites work

• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 512931 (Why is no real title available?)
• scientific article; zbMATH DE number 720183 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3102313 (Why is no real title available?)
• A Uniform Approach Towards Succinct Representation of Trees
• An algorithmic note on the gallai-milgram theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing on a free tree via complexity-preserving mappings
• Decreasing the diameter of bounded degree graphs
• Design networks with bounded pairwise distance
• Diameter bounds for altered graphs
• Diameter increase caused by edge deletion
• Efficiency of a Good But Not Linear Set Union Algorithm
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• Fundamentals of parameterized complexity
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Minimizing the diameter of a network using shortcut edges
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Parallel Shortcutting of Rooted Trees
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Shortcutting Planar Digraphs
• Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture
• Structure of polynomial-time approximation
• Succinct ordinal trees with level-ancestor queries
• Testing the diameter of graphs
• The Serial Transitive Closure Problem for Trees
• The diameter of randomly perturbed digraphs and some applications
• The parametric complexity of graph diameter augmentation
• The shortcut problem - complexity and algorithms
• Transitive-closure spanners: a survey
• Variations on the Gallai-Milgram theorem

Cited in

(5)

• The shortcut problem - complexity and algorithms
• On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
• Minimizing the diameter of a network using shortcut edges
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)

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)