Herman Haverkort

User Tools

Site Tools

unsolved_puzzles

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Last revisionBoth sides next revision
unsolved_puzzles [2019/02/02 00:35] – [Nearest-neighbour-preserving space-filling curves] administratorunsolved_puzzles [2019/09/25 10:01] – [Shortest-path-preserving rounding of weights in a graph] administrator
Line 118: Line 118:
 ===== Shortest-path-preserving rounding of weights in a graph ===== ===== Shortest-path-preserving rounding of weights in a graph =====
  
-(updated 17 January 2019) Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected planar graph //G// with non-negative weights, in which each edge is a shortest path, decide whether one can construct a copy //G'// of //G// in which all weights are replaced by integers, such that the following conditions hold:+(updated 25 September 2019) Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected planar graph //G// with non-negative weights, in which each edge is a shortest path, decide whether one can construct a copy //G'// of //G// in which all weights are replaced by integers, such that the following conditions hold:
     * the difference in weight between any shortest path in //G// and the corresponding path in //G'// is less than 1;     * the difference in weight between any shortest path in //G// and the corresponding path in //G'// is less than 1;
     * any shortest path in //G// is a shortest path in //G'//.     * any shortest path in //G// is a shortest path in //G'//.
Line 127: Line 127:
   * **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research::haverkort-cues-about-travel-time.pdf|text}} (draft of full report).   * **Embedding cues about travel time in schematic maps.**\\ By Herman Haverkort.\\ Presented at the //Schematic Mapping Workshop 2014//.\\ {{research::haverkort-cues-about-travel-time.pdf|text}} (draft of full report).
  
-We believe we have found a proof that the problem is, in general, NP-hard for non-planar graphs, and we believe we have found a polynomial-time algorithm that solves the problem for trees---we are currently writing up these results. However, from an application point of view, the case of planar graphs may be more relevant, and for planar graphs we still do not know.+The problem is, in general, NP-hard for non-planar graphs, and can be solved in polynomial time for trees: 
 + 
 +  * **Shortest-Path-Preserving Rounding.**\\ By Herman Haverkort, David Kübel, and Elmar Langetepe.\\ //Computing Research Repository (arXiv.org)//, 1905.08621, 2019.\\ [[https://arxiv.org/abs/1905.08621|text]] 
 + 
 + 
 +However, from an application point of view, the case of planar graphs may be more relevant, and for planar graphs we still do not know.
  
unsolved_puzzles.txt · Last modified: 2023/09/05 11:23 by administrator

Page Tools

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki