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
On the complexity of vertex-splitting into an interval graph
Lebanese American University, Beirut, Lebanon.
LIS, Centrale Méditerranée, Aix-Marseille Université, Marseille, France.
Université de Strasbourg, Strasbourg, 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, Proceedings / [ed] Foucaud F.; Parreau A., Cham: Springer, 2026, s. 1-15Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We introduce and study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard, even when the input is restricted to subcubic planar bipartite graphs. We further observe that vertex splitting differs fundamentally from vertex and edge deletions as graph modification operations when the objective is to obtain a chordal graph, even for graphs with maximum independent set size at most two. On the positive side, we give a polynomial-time algorithm for transforming, via a minimum number of vertex splits, a given graph into a disjoint union of paths, and that splitting triangle free graphs into unit interval graphs is also solvable in polynomial time.

Ort, förlag, år, upplaga, sidor
Cham: Springer, 2026. s. 1-15
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 16587
Nationell ämneskategori
Datavetenskap (datalogi) Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-255471DOI: 10.1007/978-3-032-27732-9_1Scopus ID: 2-s2.0-105041614770ISBN: 9783032277312 (tryckt)ISBN: 9783032277329 (digital)OAI: oai:DiVA.org:umu-255471DiVA, id: diva2:2078453
Konferens
37th International Workshop on Combinatorial Algorithms, IWOCA 2026, June 8-11, 2026, Clermont-Ferrand, France
Tillgänglig från: 2026-06-24 Skapad: 2026-06-24 Senast uppdaterad: 2026-06-24Bibliografiskt 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
Datavetenskap (datalogi)Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 7 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