Publikacje
Filtry
wszystkich: 517
Katalog Publikacji
Rok 2024
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublikacjaThe 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
PublikacjaThe 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...
-
Equitable colorings of some variation of corona products of cubic graphs
PublikacjaThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
PublikacjaW 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.
-
Quantum strategies for rendezvous and domination tasks on graphs with mobile agents
PublikacjaThis paper explores the application of quantum nonlocality, a renowned and unique phenomenon acknowledged as a valuable resource. Focusing on an alternative application, we demonstrate its quantum advantage for mobile agents engaged in specific distributed tasks without communication. The research addresses the significant challenge of rendezvous on graphs and introduces a distributed task for mobile agents grounded in the graph...
-
Semi-definite programming and quantum information
PublikacjaThis paper presents a comprehensive exploration of semi-definite programming (SDP) techniques within the context of quantum information. It examines the mathematical foundations of convex optimization, duality, and SDP formulations, providing a solid theoretical framework for addressing optimization challenges in quantum systems. By leveraging these tools, researchers and practitioners can characterize classical and quantum correlations,...
-
Teoria grafów wczoraj i dziś
PublikacjaW pracy naszkicowano kamienie milowe teorii grafów poczynając od pierwszego artykułu Eulera na temat mostów w Królewcu z połowy 18. wieku. Następnie opisano słynny problem 4 barw i jego wariacje. Pracę kończy charakterystyka najnowszych wyzwań teorii grafów.
Rok 2023
-
Complexity Issues on of Secondary Domination Number
PublikacjaIn 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
PublikacjaWe 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
PublikacjaRecently, 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
PublikacjaRendezvous 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
PublikacjaOne 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
PublikacjaThe 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.
PublikacjaW 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
PublikacjaAbstract 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
PublikacjaIntroduction 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
PublikacjaLiquid 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
PublikacjaPowracamy 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.
PublikacjaPoniż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.
PublikacjaZilustrowano 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.
PublikacjaNiniejszy 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
PublikacjaProblem 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
PublikacjaAbstract 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
Publikacja[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...
Rok 2022
-
Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublikacjaSmart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....
-
Efficacy of intralesional bleomycin in treatment resistant viral warts
PublikacjaIntroduction Optimal management of treatment-refractory viral warts caused by human papillomavirus is unknown. One of the treatment methods is intralesional bleomycin solution. Objective To determine risk factors for resistant viral warts (not responding to conventional treatments for ≥ 6 months), to determine the effectiveness and safety of intralesional bleomycin in a group of patients with viral warts resistant to conventional...
-
Global defensive secure structures
PublikacjaLet S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...
-
Grafo-ania, czyli rzecz o grafach i algorytmach. Drzewa Steinera
PublikacjaProblem: na płaszczyźnie leżą 3 punkty. Znajdź czwarty, taki że jego sumaryczna odległość od 3 pozostałych jest minimalna, Pokazujemy jak rozwiązać ten problem i jego uogólnienie.
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Liczby Ramseya
PublikacjaZdefiniowano liczby Ramseya i wskazano na trudności obliczeniowe ich wyznaczania już przy niewielkich wartościach takich liczb.
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Problem 8 hetmanów
PublikacjaW eseju spojrzano na problem 8 hetmanów na szachownicy z punktu widzenia teorii grafów
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Szybkie mnożenie macierzy
PublikacjaMiniesej zawiera komentarz na temat zastosowania sztucznej inteligencji do problemu mnożenia macierzy.
-
Hybrid no-signaling-quantum correlations
PublikacjaFundamental investigations in non-locality have shown that while the no-signaling principle alone is not sufficient to single out the set of quantum non-local correlations, local quantum mechanics and no-signaling together exactly reproduce the set of quantum correlations in the two-party Bell scenario. Here, we introduce and study an intermediate hybrid no-signaling quantum set of non-local correlations that we term HNSQ in the...
-
Infinite chromatic games
PublikacjaIn the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...
-
Non-Perfect Propagation of Information to a Noisy Environment with Self-Evolution
PublikacjaWe study the non-perfect propagation of information for evolving a low-dimensional environment that includes self-evolution as well as noisy initial states and analyse the interrelations between the degree of objectivization and environment parameters. In particular, we consider an analytical model of three interacting qubits and derive its objectivity parameters. The numerical analysis shows that the quality of the spectrum broadcast...
-
On zero-error codes produced by greedy algorithms
PublikacjaWe present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.
-
Paired domination versus domination and packing number in graphs
PublikacjaGiven a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a k-packing in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The k-packing number is the order of a largest kpacking and...
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublikacjaDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. Alicja i Bogdan w naleśnikarni
PublikacjaNiniejszym esejem inaugurujemy , po kilkuletniej przerwie, nową serię zagadek algorytmicznych.Pierwszy odcinek nosi nazwę Alicja i Bogdan w naleśnikarni.
-
Quantum security and theory of decoherence
PublikacjaWe sketch a relation between two crucial, yet independent, fields in quantum information research, viz. quantum decoherence and quantum cryptography. We investigate here how the standard cryptographic assumption of shielded laboratory, stating that data generated by a secure quantum device remain private unless explicitly published, is disturbed by the einselection mechanism of quantum Darwinism explaining the measurement process...
-
Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublikacjaThe problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublikacjaIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...
-
Significance of Dermoscopy in Association with Clinical Features in Differentiation of Basal Cell Carcinoma and Benign Trichoblastic Tumours
PublikacjaBackground: Although basal cell carcinoma (BCC) can, in the majority of cases, be diagnosed based on clinical and dermoscopic assessment, a potential overlap with benign adnexal skin tumours seems to exist, including trichoblastic tumours (TT). Methods: Retrospective analysis of clinical and dermoscopic features of benign TT and BCC cases was performed to develop a diagnostic algorithm with a potential utility in clinical practice....
-
Weighted 2-sections and hypergraph reconstruction
PublikacjaIn the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...
Rok 2021
-
Block graphs with large paired domination multisubdivision number
PublikacjaThe paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
-
Bortezomib induces methylation changes in neuroblastoma cells that appear to play a significant role in resistance development to this compound
PublikacjaThe anticancer activity of bortezomib (BTZ) has been increasingly studied in a number of indications and promising results for the use of this treatment have been shown in neuroblastoma. As BTZ treatment is usually administered in cycles, the development of resistance and side effects in patients undergoing therapy with BTZ remains a major challenge for the clinical usage of this compound. Common resistance development also means...
-
Bounds on isolated scattering number
PublikacjaThe isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.
-
Bounds on isolated scattering number
PublikacjaThe isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.
-
Closer Look at the Uncertainty Estimation in Semantic Segmentation under Distributional Shift
PublikacjaWhile recent computer vision algorithms achieve impressive performance on many benchmarks, they lack robustness - presented with an image from a different distribution, (e.g. weather or lighting conditions not considered during training), they may produce an erroneous prediction. Therefore, it is desired that such a model will be able to reliably predict its confidence measure. In this work, uncertainty estimation for the task...
-
Diagnostic Accuracy of Liquid Biopsy in Endometrial Cancer
PublikacjaBackground: Liquid biopsy is a minimally invasive collection of a patient body fluid sample. In oncology, they offer several advantages compared to traditional tissue biopsies. However, the potential of this method in endometrial cancer (EC) remains poorly explored. We studied the utility of tumor educated platelets (TEPs) and circulating tumor DNA (ctDNA) for preoperative EC diagnosis, including histology determination. Methods:...
-
Gossiping by energy-constrained mobile agents in tree networks
PublikacjaEvery node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently...
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Prawie 300 lat teorii powstałej blisko Gdańska
PublikacjaW niniejszym numerze inaugurujemy nową kolumnę popularnonaukową w dziale Edukacja. Będzie ona zawierała szkice poświęcone grafom i algorytmom dyskretnym
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Spłaszczanie grafów
PublikacjaW eseju poruszono problem rysowania grafów na płaszczyźnie.
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Twierdzenie o czterech barwach
PublikacjaPrzedstawiono istotę i historię twierdzenia o 4 barwach.
-
Grafy w Imperium Rzymskim
PublikacjaTeoria grafów znalazła zastosowanie w sieciach telekomunikacyjnych, transporcie, bioinformatyce, zarządzaniu i w wielu innych dziedzinach. Ale co ma ona wspólnego z Imperium Rzymskim?
-
Graphs hard-to-process for greedy algorithm MIN
PublikacjaWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.
-
Greencoin - educational information system for eco-inclusion and empowering urban adaptability.
PublikacjaSARS-CoV19 pandemic exposed a broad spectrum of challenges for modern cities, societies and the environment at large. The post-Covid transformation requires new social and ecological solutions, adjusted to modern challenges, but also equipped with technological advances that allow for digital inclusion and sustainable urban development to benefit the local economy and society. Many information systems are designed to enable...
-
Greencoin information system empowering urban adaptability and eco living choices.
PublikacjaThere are many gamification projects focused on mitigating climate changes which has been tested or implemented worldwide. However, the gap which remains is the limited number of solutions dedicated for central European countries where the urban polices in terms of climate vulnerability are bounded. On the other hand, cities, when implementing climate-oriented policies, are focused on urban resilience, while the opportunities...
-
Greencoin: prototype of a mobile application facilitating and evidencing pro-environmental behavior of citizens
PublikacjaAmong many global challenges, climate change is one of the biggest challenges of our times. While it is one of the most devastating problems humanity has ever faced, one question naturally arises: can individuals make a difference? We believe that everyone can contribute and make a difference to the community and lives of others. However, there is still a lack of effective strategies to promote and facilitate pro-environmental...
-
imPlatelet classifier: image‐converted RNA biomarker profiles enable blood‐based cancer diagnostics
PublikacjaLiquid biopsies offer a minimally invasive sample collection, outperforming traditional biopsies employed for cancer evaluation. The widely used material is blood, which is the source of tumor-educated platelets. Here, we developed the imPlatelet classifier, which converts RNA-sequenced platelet data into images in which each pixel corresponds to the expression level of a certain gene. Biological knowledge from the Kyoto Encyclopedia...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublikacjaAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Komputer w labiryncie
PublikacjaProgramiści piszą programy, które potrafią robić wiele różnych rzeczy: odtwarzać filmy, prognozować pogodę, pomagać w nauce języków obcych czy matematyki. Ale czy wiesz, że można zaprogramować komputer tak, aby tworzył labirynty? W dodatku takie, które zawierają tajne informacje!
-
Modelling of dark fermentation of glucose and sour cabbage
PublikacjaIn the article, modified Anaerobic Digestion Models 1 (ADM-1) was tested for modelling dark fermentation for hydrogen production. The model refitting was done with the Euler method. The new model was based on sets of differential equations. The model was checked for hydrogen production from sour cabbage in batch and semi-batch in 5 g VSS (volatile solid suspension)/L and at the semi-batch process from glucose at 5 and 10 g VSS/L....
-
On the Characteristic Graph of a Discrete Symmetric Channel
PublikacjaWe present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomial-time algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.
-
Progress on Roman and Weakly Connected Roman Graphs
PublikacjaA graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002)....
-
Quantum randomness protected against detection loophole attacks
PublikacjaDevice and semi-device-independent private quantum randomness generators are crucial for applications requiring private randomness. However, they are vulnerable to detection inefficiency attacks and this limits severely their usage for practical purposes. Here, we present a method for protecting semi-device-independent private quantum randomness generators in prepare-and-measure scenarios against detection inefficiency attacks....
-
Scheduling of compatible jobs on parallel machines
PublikacjaThe dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
PublikacjaIn this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...
-
Searching by heterogeneous agents
PublikacjaIn this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs: once a search strategy initially assigns labels to the searchers, each searcher can be only present on an edge of its own label. We prove that this problem is not monotone even for trees and we give instances...
-
Sztuczna inteligencja w onkologii - nowe narzędzia do diagnostyki i medycyny spersonalizowanej
Publikacjastatnie dekady doprowadziły do rozwoju zaawansowanych technologii badawczych, cechujących się wysoką przepustowością. Zmienia to oblicze medycyny, doprowadzając do generowania ogromnej ilości danych. Z każdym kolejnym rokiem przybywa pacjentów onkologicznych, a zebrane informacje o pacjentach przekraczają możliwości lekarzy i naukowców w zakresie samodzielnej analizy tzw. big data. Właśnie dlatego świat nauki coraz częściej zwraca...
-
T-colorings, divisibility and circular chromatic number
PublikacjaLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Total chromatic sum for trees
PublikacjaThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
PublikacjaThis paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...
-
Towards Cancer Patients Classification Using Liquid Biopsy
PublikacjaLiquid biopsy is a useful, minimally invasive diagnostic and monitoring tool for cancer disease. Yet, developing accurate methods, given the potentially large number of input features, and usually small datasets size remains very challenging. Recently, a novel feature parameterization based on the RNA-sequenced platelet data which uses the biological knowledge from the Kyoto Encyclopedia of Genes and Genomes, combined with a classifier...
-
Transcriptomic landscape of blood platelets in healthy donors
PublikacjaBlood platelet RNA-sequencing is increasingly used among the scientific community. Aberrant platelet transcriptome is common in cancer or cardiovascular disease, but reference data on platelet RNA content in healthy individuals are scarce and merit complex investigation. We sought to explore the dynamics of platelet transcriptome. Datasets from 204 healthy donors were used for the analysis of splice variants, particularly with...
-
Transcriptomic landscape of blood platelets in healthy donors
PublikacjaBACKGROUND Blood platelet RNA-sequencing is increasingly used among the scientific community. Aberrant platelet transcriptome is common in cancer or cardiovascular disease, but reference data on platelet RNA content in healthy individuals are scarce and merit complex investigation. METHODS We sought to explore the dynamics of platelet transcriptome. Datasets from 204 healthy donors were used for the analysis of splice variants,...
-
User experience and user interface (UX/UI) design of Greencoin mobile application.
PublikacjaThe aim of the Greencoin mobile application is to encourage its users to change their behavior and to act pro-ecologically. The pilot version of the application will operate within the city of Gdańsk. To keep the app’s user base as large as possible, the graphical user interface should be attractive to the broadest possible audience, and the application itself should be easy and fun to use. This work is a continuation of studies...
Rok 2020
-
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublikacjaIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm.
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
Blurred quantum Darwinism across quantum reference frames
PublikacjaQuantum Darwinism describes objectivity of quantum systems via their correlations with their environment--information that hypothetical observers can recover by measuring the environments. However, observations are done with respect to a frame of reference. Here, we take the formalism of [Giacomini, Castro-Ruiz, & Brukner. Nat Commun 10, 494 (2019)], and consider the repercussions on objectivity when changing quantum reference...
-
Chromatic cost coloring of weighted bipartite graphs
PublikacjaGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
Czy komputer może zrobić błąd rachunkowy?
PublikacjaW szkole błędy rachunkowe nie są mile widziane, w dodatku zazwyczaj nie wolno na lekcjach matematyki używać kalkulatorów. Jaka szkoda! Przecież kalkulator nigdy się nie myli! Ale czy na pewno?
-
Deep learning for recommending subscription-limited documents
PublikacjaDocuments recommendation for a commercial, subscription-based online platform is important due to the difficulty in navigation through a large volume and diversity of content available to clients. However, this is also a challenging task due to the number of new documents added every day and decreasing relevance of older contents. To solve this problem, we propose deep neural network architecture that combines autoencoder with...
-
Experimental certification of an informationally complete quantum measurement in a device-independent protocol
PublikacjaMinimal informationally complete positive operator-valued measures (MIC-POVMs) are special kinds of measurement in quantum theory in which the statistics of their d2-outcomes are enough to reconstruct any d-dimensional quantum state. For this reason, MIC-POVMs are referred to as standard measurements for quantum information.Here, we report an experiment with entangled photon pairs that certifies, for what we believe is the first...
-
Experimental test of nonclassicality with arbitrarily low detection efficiency
PublikacjaWe theoretically introduce and experimentally demonstrate the realization of a nonclassicality test that allows for arbitrarily low detection efficiency without invoking an extra assumption of independence of the devices. Our test and its implementation is set in a prepare-and-measure scenario with an upper limit on the classical communication capacity of the channel through which the systems are communicated. The essence for our...
-
Graph classes generated by Mycielskians
PublikacjaIn this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...
-
Multi-agent graph searching and exploration algorithms
PublikacjaA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
-
Paired domination subdivision and multisubdivision numbers of graphs
PublikacjaThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Shared processor scheduling of multiprocessor jobs
PublikacjaWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Tight bounds on global edge and complete alliances in trees
PublikacjaIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
-
Visual TreeCmp : Comprehensive Comparison of Phylogenetic Trees on the Web
Publikacja1. We present Visual TreeCmp—a package of applications for comparing phylogenetic tree sets. 2. Visual TreeCmp includes a graphical web interface allowing the visualization of compared trees and command line application extended by comparison methods recently proposed in the literature. 3. The phylogenetic tree similarity analysis in Visual TreeCmp can be performed using eighteen metrics, of which 11 are dedicated to rooted trees...
-
Zagadkowe obrazki binarne
PublikacjaCzy wiesz, że za pomocą liczb można kodować obrazki? Dziś odkodujemy i narysujemy takie obrazki, a przy okazji poćwiczymy zamianę liczb z systemu dziesiętnego na dwójkowy, czyli binarny.
Rok 2019
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
A Framework for Searching in Graphs in the Presence of Errors
PublikacjaWe consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...
-
Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines
PublikacjaThe goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...
-
Building a Nest by an Automaton
PublikacjaA robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot...
-
Clearing directed subgraphs by mobile agents
PublikacjaWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
Cops, a fast robber and defensive domination on interval graphs
PublikacjaThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Cztery algorytmy, które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublikacjaOdcinek ten poświęcony jest problemowi programowania liniowego oraz problemowi badania liczb pierwszych.
-
Cztery algorytmy, które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublikacjaW ostatniej części tryptyku poruszamy problem przyjaznego rysowania grafów oraz prezentujemy algorytmy dla szybkiego mnożenia macierzy. Nasze rozważania kończymy ilustracją postępu w dziedzinie sprzętu i oprogramowania