-
Graphs with two moplexes [Elektronski vir]Dallard, Clément Jean ...Mopleksi so naravne grafovske strukture, na katere lahko gledamo kot posplošitev Diracovega klasičnega izreka o tetivnih grafih, na splošne grafe. Znano je, da je ta pojem tesno povezan z ... leksikografskim iskanjem v grafih, pa tudi z asteroidnimi trojkami, in je bil uporabljen v več algoritmih, povezanih z razredi grafov, kot so intervalni grafi, grafi brez krempljev in grafi brez diamantov. Čeprav ima vsak graf, ki ni poln, vsaj dva mopleksa, je malo znanega o strukturnih lastnostih grafov z omejenim številom mopleksov. Preučevanje teh grafov je med drugim motivirano s primerjavo med mopleksi v splošnih grafih in simplicialnimi moduli v tetivnih grafih: veliko je namreč znanega o tetivnih grafih z omejenim številom simplicialnih modulov (na primer, tetivni grafi, ki imajo največ dva simplicialna modula, so intervalni). Po drugi strani o grafih z omejenim številom mopleksov vemo zelo malo. V tem delu začnemo z raziskavo ▫$k$▫-mopleksnih grafov, ki so definirani kot grafi, ki vsebujejo največ ▫$k$▫ mopleksov. Posebej zanimiv je najmanjši netrivialni primer, ▫$k = 2$▫, ki ustreza razredu intervalnih grafov. Kot naš glavni strukturni rezultat pokažemo, da je razred povezanih 2-mopleksnih grafov umeščen med razred pravih intervalnih grafov in razred koprimerljivostnih grafov; poleg tega sta obe vključitvi tesni za hereditarne razrede. Z vidika teorije kompleksnosti to vodi do naravnega vprašanja, ali prisotnost največ dveh mopleksov zagotavlja zadostno količino strukture za učinkovito reševanje problemov, za katere je znano, da so nerešljivi na grafih koprimerljivosti, ne pa tudi na pravih intervalnih grafih. Razvijemo nove prevedbe, ki na to vprašanje odgovarjajo negativno za dva relevantna problema, in sicer izomorfizem grafa in problem največjega prereza. Poleg tega za grafe z večjim številom mopleksov posplošimo prej znani rezultat, da imajo grafi brez asteroidnih trojk največ dva mopleksa na bolj splošno trdivev za večje asteroidne množice. Obravnavamo tudi zadostne pogoje za obstoj hamiltonskih poti v 2-mopleksnih grafih ter nekatere druge povezave z izogibnimi vozlišči.Source: Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium [Elektronski vir] (Str. 248-256)Type of material - conference contribution ; adult, seriousPublish date - 2021Language - englishCOBISS.SI-ID - 93541123
Author
Dallard, Clément Jean |
Ganian, Robert |
Hatzel, Meike |
Krnc, Matjaž, 1987- |
Milanič, Martin, 1980-
Topics
mopleks |
simplicialno vozlišče |
izogibno vozlišče |
asteroidno število |
koprimerljivostni graf |
hamiltonska pot |
moplex |
simplicial vertex |
avoidable vertex |
asteroidal number |
cocomparability graph |
Hamiltonian path
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dallard, Clément Jean | 53750 |
Ganian, Robert | |
Hatzel, Meike | |
Krnc, Matjaž, 1987- | 34562 |
Milanič, Martin, 1980- | 30211 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.