On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph

DOI10.1016/j.disopt.2010.09.008zbMath1244.05124OpenAlexW2052434346MaRDI QIDQ429689

Refael Hassin, Nili Guttmann-Beck

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.008

zbMATH Keywords

edge coloringextremal graph theorynetwork upgrading

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Matching interdiction
• A simple heuristic for the p-centre problem
• A heuristic for the p-center problem in graphs
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Finding the most vital node of a shortest path.
• Augmenting forests to meet odd diameter requirements
• A Best Possible Heuristic for the k-Center Problem
• Shortest-path network interdiction
• Upgrading trees under diameter and budget constraints
• Increasing the Weight of Minimum Spanning Trees
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• The network inhibition problem
• Upgrading arcs to minimize the maximum travel time in a network
• Oriented graph coloring