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

DOI10.1016/j.disopt.2010.09.008zbMath1244.05124MaRDI 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 coloring; extremal graph theory; network upgrading

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

05C12: Distance in graphs

68W25: Approximation algorithms

05C20: Directed graphs (digraphs), tournaments

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