Problem geodetskega pokritja povezav grafa ?$G$? je poiskati najmanjše število najkrajših poti, ki pokrivajo množico povezav grafa ?$G$?. Problem ?$k$?-splošne lege za povezave je uveden kot problem iskanja največje množice ?$S$? povezav grafa ?$G$?, tako da največ ?$k-1$? povezav iz ?$S$? leži na skupni najkrajši poti. Pokažemo, da sta to dualna min-max problema, in ju povežemo s problemom povezavne geodetske razdelitve. S temi zvezami določimo natančne vrednosti števila ?$k$?-splošne lege za povezave za različne vrednosti ?$k$? in za različna omrežja, vključno s torusnimi grafi, hiperkockami in Benešovimi omrežji.

URN

URN:NBN:SI:DOC-WA2P4H1M

COBISSID

226849283

DOI

10.26493/2590-9770.1745.5f4

Objavljeno

21.03.2025

Metapodatki

Citiranje

APA:

Manuel, Paul, Prabha, R., Klavžar, Sandi (2025). Generalization of edge general position problem. The art of discrete and applied mathematics, letnik 8, številka 1 article p1.02, 12 str. URN:NBN:SI:DOC-WA2P4H1M from http://www.dlib.si

MLA:

Manuel, Paul, Prabha, R., Klavžar, Sandi. "Generalization of edge general position problem." The art of discrete and applied mathematics letnik 8. številka 1 article p1.02 (2025) 12 str..
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-WA2P4H1M>