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

DOI10.1016/J.DISOPT.2010.09.008zbMATH Open1244.05124OpenAlexW2052434346MaRDI QIDQ429689FDOQ429689

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

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

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)

Cites Work

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

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)