Full metadata record
DC poleHodnotaJazyk
dc.contributor.authorGavrilyuk, Alexander
dc.contributor.authorNedela, Roman
dc.contributor.authorPonomarenko, Ilia
dc.date.accessioned2023-09-04T10:00:23Z-
dc.date.available2023-09-04T10:00:23Z-
dc.date.issued2023
dc.identifier.citationGAVRILYUK, A. NEDELA, R. PONOMARENKO, I. The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs. GRAPHS AND COMBINATORICS, 2023, roč. 39, č. 4, s. nestránkováno. ISSN: 0911-0119cs
dc.identifier.issn0911-0119
dc.identifier.uri2-s2.0-85165259992
dc.identifier.urihttp://hdl.handle.net/11025/53899
dc.description.abstractGraf nazýváme distančně dědičný když v libovolném souvislém indukovaném podgrafe je vzdálenost dvou vrcholů rovnaká jako v původním grafu. V článku dokážeme, že WL-dimenze distnčně dědičných grafů je dva.cs
dc.format
dc.format19 s.cs
dc.format.mimetypeapplication/pdf
dc.language.iso
dc.language.isoenen
dc.publisherSpringeren
dc.relation.ispartofseriesGraphs And Combinatoricsen
dc.rights© The Author(s)en
dc.subjectdistančně dědičné grafycs
dc.subjectWL-dimenzecs
dc.subjectisomorfismus grafůcs
dc.titleThe Weisfeiler-Leman Dimension of Distance-Hereditary Graphsen
dc.title.alternativeWL-dimenze distančně dědičných grafůcs
dc.typečlánekcs
dc.typearticleen
dc.rights.accessopenAccessen
dc.type.versionpublishedVersionen
dc.description.abstract-translatedA graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Leman algorithm tests the isomorphism of any two graphs if one of them is distance-hereditary; more precisely, the Weisfeiler-Leman dimension of the class of finite distance-hereditary graphs is equal to 2. The previously best known upper bound for the dimension was 7.en
dc.subject.translateddistance-hereditary graphen
dc.subject.translatedWeisfeiler-Leman dimensionen
dc.subject.translatedgraph isomorphismen
dc.identifier.doi10.1007/s00373-023-02683-3
dc.type.status
dc.type.statusPeer-revieweden
dc.identifier.document-number1025337200001
dc.identifier.obd43940051
Vyskytuje se v kolekcích:Články / Articles (NTIS)
Články / Articles (KMA)
OBD

Soubory připojené k záznamu:
Soubor VelikostFormát 
WLdimhereditarygraphs.pdf349,16 kBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/53899

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD