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: 267; Prenosov: 4
 Celotno besedilo (1,45 MB)
Gradivo ima več datotek! Več... |
2. |
3. |
4. Planarity testing algorithms : zaključna nalogaUroš Babić, 2025, diplomsko delo Ključne besede: graph planarity, planarity testing, Boyer–Myrvold algorithm, Kuratowski/Wagner theorem, depth-first search (DFS), lowpoint values, articulation points, biconnected components, graph embedding, graph6 format
Objavljeno v RUP: 04.10.2025; Ogledov: 331; Prenosov: 0 |
5. On reduced Hamilton walksAleksander Malnič, Rok Požar, 2026, izvirni znanstveni članek Opis: A Hamilton walk in a finite graph is a walk, either open or closed, that traverses every vertex at least once. Here, we introduce Hamilton walks that are reduced in the sense that they avoid immediate backtracking: a reduced Hamilton walk never traverses the same edge forth and back consecutively. While every connected graph admits a Hamilton walk, existence of a reduced Hamilton walk is not guaranteed for all graphs. However, we prove that a reduced Hamilton walk does exist in a connected graph with minimal valency at least 2. Furthermore, given such a graph on n vertices, we present an O(n2)-time algorithm that constructs a reduced Hamilton walk of length at most n(n+3)/2. Specifically, for a graph belonging to a family of regular expander graphs, we can find a reduced Hamilton walk of length at most c(6n−2)logn+2n, where c is a constant independent of n.
Ključne besede: algorithm, Hamilton walk, nonstandard metric, reduced walk
Objavljeno v RUP: 09.09.2025; Ogledov: 494; Prenosov: 7
Celotno besedilo (1,91 MB)
Gradivo ima več datotek! Več... |
6. |
7. |
8. Testing whether the lifted group splitsRok Požar, 2016, izvirni znanstveni članek Opis: Let a group of automorphisms lift along a regular covering projection of connected graphs given combinatorially by means of voltages. The data that determine the lifted group and its action are then conveniently encoded in terms of voltages as well. Along these lines, an algorithm for testing whether the lifted group is a split extension of the group of covering transformations has recently been proposed in the case when the group of covering transformations is solvable. It consists of decomposing the covering into a series of coverings with elementary abelian groups of covering transformations, and inductively solving the problem at every elementary abelian step. Although the explicit construction of the lifted group is not needed, it still involves time and space consuming constructions of certain subgroups in the lifted group at every step except at the final one. In this paper, an improved version that completely avoids such constructions is presented. From voltage distribution we first compute the weak action and the factor set that determine the lifted group, and we then carry out the test by extracting the necessary information only from the corresponding weak actions and factor sets at every step. An experimental comparison is made against the previous version.
Ključne besede: algorithm, graph, group extension, lifting automorphisms, regular covering projection, voltages
Objavljeno v RUP: 03.01.2022; Ogledov: 2323; Prenosov: 39
Celotno besedilo (317,95 KB) |
9. |
10. On applications of quantum algorithms in cryptanalysis of block ciphers : master's thesisDraženka Višnjić, 2021, magistrsko delo Ključne besede: quantum algorithms, cryptanalysis of block ciphers, postquantum analysis, Simon's algorithm, Grover's algorithm, Bernstein-Vazirani's algorithm, Kuperberg's algorithm, Feistel network, SPN, FX
Objavljeno v RUP: 18.10.2021; Ogledov: 3251; Prenosov: 48
 Povezava na celotno besedilo |
