Publications
Filters
total: 513
Catalog Publications
Year 2024
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublicationThe problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...
-
Deep Learning-Based, Multiclass Approach to Cancer Classification on Liquid Biopsy Data
PublicationThe field of cancer diagnostics has been revolutionized by liquid biopsies, which offer a bridge between laboratory research and clinical settings. These tests are less invasive than traditional biopsies and more convenient than routine imaging methods. Liquid biopsies allow studying of tumor-derived markers in bodily fluids, enabling the development of more precise cancer diagnostic tests for screening, disease monitoring, and...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
PublicationW kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.
Year 2023
-
Complexity Issues on of Secondary Domination Number
PublicationIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
Edge and Pair Queries-Random Graphs and Complexity
PublicationWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Edge coloring of graphs of signed class 1 and 2
PublicationRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
Entangled rendezvous: a possible application of Bell non-locality for mobile agents on networks
PublicationRendezvous is an old problem of assuring that two or more parties, initially separated, not knowing the position of each other, and not allowed to communicate, are striving to meet without pre-agreement on the meeting point. This problem has been extensively studied in classical computer science and has vivid importance to modern and future applications. Quantum non-locality, like Bell inequality violation, has shown that in many...
-
Experimental certification of more than one bit of quantum randomness in the two inputs and two outputs scenario
PublicationOne of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing...
-
Generalization of Phylogenetic Matching Metrics with Experimental Tests of Practical Advantages
PublicationThe ability to quantify a dissimilarity of different phylogenetic trees is required in various types of phylogenetic studies, for example, such metrics are used to assess the quality of phylogeny construction methods and to define optimization criteria in supertree building algorithms. In this article, starting from the already described concept of matching metrics, we define three new metrics for rooted phylogenetic trees. One...
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Gry chromatyczne na grafach.
PublicationW minieseju analizujemy grę 2-osobową, polegającą na tym, że Alicja i Bogdan współdziałają by pomalować mapę narysowaną na płaszczyźnie.
-
Longitudinal drug synergy assessment using convolutional neural network image-decoding of glioblastoma single-spheroid cultures
PublicationAbstract Background In recent years, drug combinations have become increasingly popular to improve therapeutic outcomes in various diseases, including difficult to cure cancers such as the brain cancer glioblastoma. Assessing the interaction between drugs over time is critical for predicting drug combination effectiveness and minimizing the risk of therapy resistance. However, as viability readouts of drug combination experiments...
-
Long-term mortality after transcatheter aortic valve implantation for aortic stenosis in immunosuppression-treated patients: a propensity-matched multicentre retrospective registry-based analysis
PublicationIntroduction Data regarding patients with a previous medical record of immunosuppression treatment who have undergone transcatheter aortic valve implantation (TAVI) are limited and extremely inconclusive. Available studies are mostly short term observations; thus there is a lack of evidence on efficacy and safety of TAVI in this specific group of patients. Aim To compare the in-hospital and long-term outcomes between patients...
-
Platelet RNA Sequencing Data Through the Lens of Machine Learning
PublicationLiquid biopsies offer minimally invasive diagnosis and monitoring of cancer disease. This biosource is often analyzed using sequencing, which generates highly complex data that can be used using machine learning tools. Nevertheless, validating the clinical applications of such methods is challenging. It requires: (a) using data from many patients; (b) verifying potential bias concerning sample collection; and (c) adding interpretability...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
PublicationPowracamy tutaj do zagadki sprzed 4 lat pod tym samym tytułem, którą uzupełniamy nowymi komentarzami i nowymi zagadkami na ten temat. Pozwala to nam zilustrować szerzej zasady działania algorytmu zachłannego.
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 3. Alicja i Bogdan remontują mieszkanie.
PublicationPoniższe zagadki nawiązują z jednej strony do problemu kafelkowania płaszczyzny, który jest nierozstrzygalny, z drugiej do problemu rozkroju wstęgi, który jest NP-trudny. Jednakże przypadki szczególne, które tu rozważamy, nie są tak trudne i mogą być rozwiązane za pomocą algorytmów działających w czasie wielomianowym.
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 4. Alicja i Bogdan w samochodzie.
PublicationZilustrowano problem przeszukiwania obiektów w nieznanych przestrzeniach na przykładzie jazdy samochodem.
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 5. Alicja kupuje buty.
PublicationNiniejszy miniesej pokazuje, w jaki sposób można efektywnie przeszukiwać uporządkowane tablice 2-wymiarowe oraz, w jaki sposób można radzić sobie (niekiedy) z trudnymi problemami obliczeniowymi.
-
Rekordowe liczby pierwsze
PublicationProblem liczb pierwszych ma długą historię sięgającą czasów starożytnych. W śród liczb całkowitych liczby pierwsze grają rolę analogiczną do pierwiastków w chemii.
-
Screening of predicted synergistic multi-target therapies in glioblastoma identifies new treatment strategies
PublicationAbstract Background IDH-wildtype glioblastoma (GBM) is a highly malignant primary brain tumor with a median survival of 15 months after standard of care, which highlights the need for improved therapy. Personalized combination therapy has shown to be successful in many other tumor types and could be beneficial for GBM patients. Methods We performed the largest drug combination screen to date in GBM, using a high-throughput effort...
-
Security of Cryptocurrencies: A View on the State-of-the-Art Research and Current Developments
Publication[Context] The goal of security is to protect digital assets, devices, and services from being disrupted, exploited or stolen by unauthorized users. It is also about having reliable information available at the right time. [Motivation] Since the inception in 2009 of the first cryptocurrency, few studies have been undertaken to analyze and review the state-of-the-art research and current developments with respect to the security...