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

DOI10.1016/J.DISOPT.2010.09.008MaRDI QIDQ429689zbMATHOpenAlexFDO

Authors Nili Guttmann-Beck, Refael Hassin

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

extremal graph theoryedge coloringnetwork upgrading

Mathematics Subject Classification ID

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

Recommendations

• Decreasing the diameter of cycles
• Shortcutting directed and undirected networks with a degree constraint
• Edge addition and edge deletion of graphs
• scientific article; zbMATH DE number 2079397
• Improved approximability and non-approximability results for graph diameter decreasing problems

Cites work

• scientific article; zbMATH DE number 9246 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A heuristic for the p-center problem in graphs
• A simple heuristic for the p-centre problem
• Augmenting forests to meet odd diameter requirements
• Finding the most vital node of a shortest path.
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Increasing the Weight of Minimum Spanning Trees
• Matching interdiction
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Oriented graph coloring
• Shortest-path network interdiction
• The network inhibition problem
• Upgrading arcs to minimize the maximum travel time in a network
• Upgrading trees under diameter and budget constraints

Cited in

(1)

• A lower bound on the size of an absorbing set in an arc-coloured tournament

This page was built for publication: On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429689)