Wappler, Markus : k-best solutions under Distance Constraints in Graphs

Author(s):

Wappler, Markus

Title:

k-best solutions under Distance Constraints in Graphs

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 8, 2002

Mathematics Subject Classification:

05B35			[ Matroids, geometric lattices ]
05C12			[ Distance in graphs ]
52C45			[ Combinatorial complexity of geometric structures ]
90B40			[ Search theory ]
90B50			[ Management decision making, including multiple objectives ]

Abstract:

Based on former papers about valuated (Delta-)matroids we introduce the concept of a valuation of a graph. It is proved that in valuated Hamming graphs, a best solution as well as a 2-best solution with a given distance to the best solution can be reached via local research on shortest paths. Valuations of cubes are classified.

Keywords:

Combinatorial optimization, distance constraints, valuated (Delta-)matroids, Hamming graphs, cubes, convexity in graphs, local search, concave functions

Language:

German

Publication time:

8 / 2002