1. 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: 879; Prenosov: 17 Celotno besedilo (317,95 KB) |
2. |
3. |
4. |
5. |
6. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, izvirni znanstveni članek Ključne besede: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, strongly perfect graph, CIS graph, NP-hard problem, polynomial-time algorithm, Erdős-Hajnal property Objavljeno v RUP: 17.12.2020; Ogledov: 1398; Prenosov: 50 Povezava na celotno besedilo |
7. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, objavljeni znanstveni prispevek na konferenci Ključne besede: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, CIS graph, NP-hard problem, linear-time algorithm, Erdős-Hajnal property Objavljeno v RUP: 10.11.2020; Ogledov: 1476; Prenosov: 41 Povezava na celotno besedilo |
8. 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: 1498; Prenosov: 34 Povezava na celotno besedilo |
9. Mind the independence gapTinaz Ekim, Didem Gozüpek, Ademir Hujdurović, Martin Milanič, 2020, izvirni znanstveni članek Ključne besede: maximal independent set, independent dominating set, well-covered graph, hereditary independence gap, polynomial-time algorithm, NP-hard problem Objavljeno v RUP: 19.05.2020; Ogledov: 1756; Prenosov: 57 Povezava na celotno besedilo |
10. |