| Naslov: | On the proper interval completion problem within some chordal subclasses |
|---|
| Avtorji: | ID Dross, François (Avtor)
ID Hilaire, Claire (Avtor)
ID Koch, Ivo (Avtor)
ID Leoni, Valeria Alejandra (Avtor)
ID Pardal, Nina (Avtor)
ID Lopez Pujato, María Inés (Avtor)
ID Fernandes dos Santos, Vinicius (Avtor) |
|---|
| Datoteke: |  RAZ_Dross_Francois_2025.pdf (824,75 KB)
MD5: 5C5BFD7A9C8D8F83829B6108263FAF36
 https://doi.org/10.1016/j.disc.2024.114274
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
|
|---|
| Opis: | Given a property (graph class) Π, a graph G, and an integer k, the Π-completion problem consists of deciding whether we can turn G into a graph with the property Π by adding at most k edges to G. The Π-completion problem is known to be NP-hard for general graphs when Π is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class. |
|---|
| Ključne besede: | proper interval completion, split graph, threshold graph, quasi-threshold graph, caterpillar |
|---|
| Datum objave: | 07.10.2024 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 1-15 |
|---|
| Številčenje: | Vol. 348, iss. 1, [article no.] 114274 |
|---|
| PID: | 20.500.12556/RUP-21529  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2024.114274 |
|---|
| COBISS.SI-ID: | 218515203 |
|---|
| Datum objave v RUP: | 06.08.2025 |
|---|
| Število ogledov: | 394 |
|---|
| Število prenosov: | 6 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
