1. On the proper interval completion problem within some chordal subclassesFrançois Dross, Claire Hilaire, Ivo Koch, Valeria Alejandra Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes dos Santos, 2025, izvirni znanstveni članek 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
Objavljeno v RUP: 06.08.2025; Ogledov: 523; Prenosov: 9
 Celotno besedilo (824,75 KB)
Gradivo ima več datotek! Več... |
2. Edge elimination and weighted graph classesJesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, objavljeni znanstveni prispevek na konferenci Ključne besede: edge elimination, weighted graph, split graph, threshold graph, chain graph, linear-time recognition algorithm
Objavljeno v RUP: 10.11.2020; Ogledov: 3158; Prenosov: 38
 Povezava na celotno besedilo |
3. Linear separation of connected dominating sets in graphsNina Chiarelli, Martin Milanič, 2019, izvirni znanstveni članek Ključne besede: connected dominating set, connected domination, connected-domishold graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1-Sperner hypergraph, threshold hypergraph, threshold Boolean function, polynomial-time algorithm
Objavljeno v RUP: 04.04.2019; Ogledov: 5036; Prenosov: 167
Celotno besedilo (648,51 KB) |
4. Decomposing 1-Sperner hypergraphs, with applications to graphs, Journée-séminaire de combinatoire (équipe CALIN du LIPN, Université Paris-Nord, Villetaneuse), 11. 9. 2018Martin Milanič, 2018, predavanje na tuji univerzi Ključne besede: 1-Sperner hypergraph, threshold hypergraph, decomposition, threshold graph, clique-width
Objavljeno v RUP: 30.09.2018; Ogledov: 4762; Prenosov: 27
Povezava na celotno besedilo |
5. Decomposing 1-Sperner hypergraphs, with applications to graphs, Séminaires du Pôle 2 : Optimisation combinatoire, algorithmique", LAMSADE, Université Paris-Dauphine, 17. 9. 2018Martin Milanič, 2018, predavanje na tuji univerzi Ključne besede: 1-Sperner hypergraph, threshold hypergraph, decomposition, threshold graph, clique-width
Objavljeno v RUP: 30.09.2018; Ogledov: 3802; Prenosov: 30
Povezava na celotno besedilo |
6. |
7. |
