Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An algorithm for monitoring edge-geodetic sets in chordal graphs
Univ Lyon, EnsL, UCBL, CNRS, LIP, LYON Cedex 07, France.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2026 (Engelska)Ingår i: Combinatorial algorithms: 37th International workshop, IWOCA 2026, Clermont-Ferrand, France, June 8–11, 2026, proceedings / [ed] Florent Foucaud; Aline Parreau, Cham: Springer, 2026, s. 442-455Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices M such that if any edge is removed, then the distance between some two vertices of M increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimum meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimum meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimal meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al.

Ort, förlag, år, upplaga, sidor
Cham: Springer, 2026. s. 442-455
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 16587
Nyckelord [en]
Chordal graphs, Monitoring edge-geodetic, Polynomial-time algorithm
Nationell ämneskategori
Diskret matematik Sannolikhetsteori och statistik
Identifikatorer
URN: urn:nbn:se:umu:diva-256580DOI: 10.1007/978-3-032-27732-9_31Scopus ID: 2-s2.0-105041631522ISBN: 978-3-032-27731-2 (tryckt)ISBN: 978-3-032-27732-9 (digital)OAI: oai:DiVA.org:umu-256580DiVA, id: diva2:2086789
Konferens
37th International Workshop on Combinatorial Algorithms, IWOCA 2026, Clermont-Ferrand, France, June 8-11, 2026
Tillgänglig från: 2026-07-16 Skapad: 2026-07-16 Senast uppdaterad: 2026-07-16Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Oijid, Nacim

Sök vidare i DiVA

Av författaren/redaktören
Oijid, Nacim
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematikSannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 4 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf