LOCATION PROBLEMS ON d - CONVEX SIMPLE PLANAR GRAPHS

Abstract

The article examines the center and median problems on graphs with special structure. In scientific works these are frequently called location problems on graphs. Although efficient solutions for graphs with some well-known properties have been found, in general case the problem remains complex. In this paper the structure of median and center in a d-convex simple planargraph Gis studied.We evaluate the connection between median/center of a graph Gwith mentioned properties and median/center of a tree, determined by G.

În articol este examinată problema centrului şi problema medianei, cunoscute în literatura de specialitate ca probleme de amplasare. Fiind, în caz general, probleme dificile, acestea se rezolvă în mod eficient pe structuri matematice speciale. În lucrare se prezintă un studiu complex cu privire la structura medianei şi centrului într-un graf planar d-convex simplu G.Este studiată legătura dintre mediana/centrul grafului şi mediana/centrul unui arbore, determinat de G.