ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • A general position problem in graph theory
    Manuel, Paul ; Klavžar, Sandi
    V klasičnem "no-three-in-line" problemu želimo poiskati največje število točk, ki jih lahko postavimo na ▫$n \times n$▫ mrežo, tako da nobene tri točke ne ležijo na skupni premici. Splošnejši problem ... za dano nmožico točk ▫$S$▫ v ravnini sprašuje, kolikšna je največja podmnožica točk ▫$S'$▫ od ▫$S$▫, tako da nobena trojica ni kolinearna. Motivirani s tema problemoma v tem članku vpeljemo naseldnjo grafovsko inačico problema. Za dani graf ▫$G$▫ določi največjo podmnožico vozlišč ▫$S$▫, tako da nobena trojica iz množice ▫$S$▫ ne leži na najkrajši poti v ▫$G$▫. Taki množici pravimo gp-množica grafa ▫$G$▫, njena velikost je gp-število ▫${\rm gp}(G)$▫ grafa ▫$G$▫. Dokazane so zgornje meje za ▫${\rm gp}(G)$▫ izražene z različnimi izometričnimi pokritji. Meje so uporabljene za določitev gp-števila različnih razredov grafov. Raziskovane so povezave med množicami vozlišč v splošni legi in pakiranji. Kot posledica so dokazane spodnje meje za gp-število. Dokazano je tudi, da je problem splošne lege NP-poln.
    Source: Bulletin of the Australian Mathematical Society. - ISSN 0004-9727 (Vol. 98, iss. 2, Oct. 2018, str. 177-187)
    Type of material - article, component part ; adult, serious
    Publish date - 2018
    Language - english
    COBISS.SI-ID - 18443609

    Link(s):

    https://doi.org/10.1017/S0004972718000473
    DOI

Shelf entry