Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Combinatorial Algorithms - 37th International Workshop, IWOCA 2026, Proceedings / [ed] Foucaud F.; Parreau A., Cham: Springer, 2026, s. 1-15Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Cham: Springer, 2026. s. 1-15
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 16587
HSV kategori
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
Konferanse
37th International Workshop on Combinatorial Algorithms, IWOCA 2026, June 8-11, 2026, Clermont-Ferrand, France
Tilgjengelig fra: 2026-06-24 Laget: 2026-06-24 Sist oppdatert: 2026-06-24bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Oijid, Nacim

Søk i DiVA

Av forfatter/redaktør
Oijid, Nacim
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 15 treff
RefereraExporteraLink to record
Permanent link

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