1. Computing tree decompositions with small independence numberClément Jean Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Martin Milanič, 2026, izvirni znanstveni članek Opis: The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum-weight independent set, can be solved in time n^O(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in SODA 2018, gave an algorithm that, given an n-vertex graph G and an integer k, in time n^O(k^3) either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-complete to decide whether a given graph has the tree-independence number at most k.
Ključne besede: tree-independence number, approximation, parameterized algorithm
Objavljeno v RUP: 16.12.2025; Ogledov: 237; Prenosov: 3
 Celotno besedilo (1,45 MB)
Gradivo ima več datotek! Več... |
2. On ▫$L^2$▫ approximation by planar Pythagorean-hodograph curvesRida T. Farouki, Marjetka Knez, Vito Vitrih, Emil Žagar, 2025, izvirni znanstveni članek Opis: The ▫$L^2$▫ approximation of planar curves by Pythagorean-hodograph (PH) polynomial curves is addressed, based on the distance defined by a metric for planar curves represented as complex valued functions of a real parameter. Because of the nonlinear nature of polynomial PH curves, constructing ▫$L^2$▫ approximants involves solving a nonlinear optimization problem. However, a simplified method that requires only the solution of a linear system may be developed by formulating the ▫$L^2$▫ approximation in the preimage space. The extension of the methodology to approximation by PH B-spline curves is also addressed, and several examples are provided to illustrate its implementation and potential.
Ključne besede: ▫$L^2$▫ approximation, complex polynomial, Pythagorean-hodograph curve, Pythagorean-hodograph spline, preimage
Objavljeno v RUP: 30.05.2025; Ogledov: 2271; Prenosov: 14
Celotno besedilo (1,33 MB)
Gradivo ima več datotek! Več... |
3. |
4. Scaffolding problems revisited : complexity, approximation and fixed parameter tractable algorithms, and some special casesMathias Weller, Annie Chateau, Clément Jean Dallard, Rodolphe Giroudeau, 2018, izvirni znanstveni članek Ključne besede: complexity, approximation, lower bound, kernel, scaffolding, {ISK4, wheel}-free graph
Objavljeno v RUP: 11.02.2020; Ogledov: 2917; Prenosov: 65
 Povezava na celotno besedilo |
5. |
6. |
7. Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2017, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3818; Prenosov: 125
Povezava na celotno besedilo |
8. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2018, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3618; Prenosov: 105
Celotno besedilo (1,44 MB)
Gradivo ima več datotek! Več... |
9. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremMartin Milanič, 2018, objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje) Ključne besede: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3426; Prenosov: 22
Povezava na celotno besedilo |
10. Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theoremAdemir Hujdurović, Edin Husić, Martin Milanič, Romeo Rizzi, Alexandru I. Tomescu, 2018, izvirni znanstveni članek Ključne besede: perfect phylogeny, minimum conflict-free row split problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, APXhardness
Objavljeno v RUP: 08.05.2018; Ogledov: 4126; Prenosov: 162
Povezava na celotno besedilo |
