Filters
total: 171
filtered: 86
Search results for: COMBINATORICS
-
Computations of the least number of periodic points of smooth boundary-preserving self-maps of simply-connected manifolds
PublicationLet $r$ be an odd natural number, $M$ a compact simply-connected smooth manifold, $\dim M\geq 4$, such that its boundary $\partial M$ is also simply-connected. We consider $f$, a $C^1$ self-maps of $M$, preserving $\partial M$. In [G. Graff and J. Jezierski, Geom. Dedicata 187 (2017), 241-258] the smooth Nielsen type periodic number $D_r(f;M,\partial M)$ was defined and proved to be equal to the minimal number of $r$-periodic points...
-
The complexity of bicriteria tree-depth
PublicationThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
Extending Service Selection Algorithms with Interoperability Analysis
PublicationApplication development by integration of existing, atomic services reduces development cost and time by extensive reuse of service components. In Service Oriented Architecture, there exist alternative versions of services supplying the same functionality but differing in Quality of Service (QoS) attributes, which enables developers to select services with optimal QoS. Existing algorithms of service selection focus on the formal...
-
Theoretical Study on Interactions of Bicyclic Vasopressin Analogues with Human Neurohypophyseal Hormone Receptors
Publication -
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
An Influence of the Aromatic Side Chains Conformations in Positions 2 and 3 of Vasopressin Analogs on Interactions with Vasopressin and Oxytocin Receptors
Publication -
Molecular Modeling of Meta II Rhodopsin
Publication -
Molecular Modeling of Interaction of the Vasopressin Analogs with Vasopressin and Oxytocin Receptors
Publication -
Study of New Oxytocin Antagonist Barusiban (Fe200 440) Affinity Toward Human Oxytocin Receptor Versus Vasopressin V1a and V2 Receptors - Molecular Dynamics Simulation in POPC Bilayer
Publication -
Molecular Dynamics of Complexes of Atosiban with Neurohypophyseal Receptors in the Fully Hydrated Phospholipid Bilayer
Publication -
Packing [1,Delta]-factors in graphs of small degree
PublicationRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
An O ( n log n ) algorithm for finding edge span of cacti
PublicationLet G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
Zero-visibility cops and robber and the pathwidth of a graph
PublicationWe examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...
-
Secure Italian domination in graphs
PublicationAn Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...
-
On zero-error codes produced by greedy algorithms
PublicationWe 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
PublicationGiven 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...
-
Cure kinetics of epoxy/MWCNTs nanocomposites: Isothermal calorimetric and rheological analyses
PublicationA combinatorial route has been applied in cure kinetics study of epoxy nanocomposites containing multi-walled carbon nanotubes (MWCNTs) based on differential scanning calorimetry and rheokinetic analyses under isothermal conditions. Pristine and amine-modified MWCNTs bearing primary and secondary amines were used at very low concentrations (0.1 and 0.3 wt.% based on epoxy weight). Model-free and model-fitting methods were applied...
-
Non-Least Square GNSS Positioning Algorithm for Densely Urbanized Areas
PublicationThe paper introduces an essentially new algorithm for calculating the GNSS position as an alternative to the least-square method. The proposed approach can be widely applied to any positioning method that uses multiple position lines for position calculation and is an example ofhow using a numerical solution can improve position accuracy without access to historical data. In essence, the method is based on the adaptation of the...
-
Certified domination
PublicationImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...
-
Interoperability Constraints in Service Selection Algorithms
PublicationIn Service Oriented Architecture, composite applications are developed by integration of existing, atomic services that may be available in alternative versions realizing the same functionality but having different Quality of Service (QoS) attributes. The development process requires effective service selection algorithms that balance profits and constraints of QoS attributes. Additionally, services operate in a heterogeneous environment,...
-
The complexity of node blocking for dags
PublicationRozważamy następującą grę (pomiędzy dwoma graczami) kombinatoryczną o nazwie ''node blocking''. Dany jest graf skierowany. Każdy wierzchołek może być zajęty przez co najwyżej jeden token. Wyróżniamy dwa kolory tokenów, biały i czarny, każdy gracz może przemieszczać tylko własne tokeny. Gracze wykonują ruchy naprzemiennie. Ruch polega na wyborze dowolnego tokena własnego koloru i przesunięciu go na dowolnego niezajętego przez inny...
-
Comparison and Analysis of Service Selection Algorithms
PublicationIn Service Oriented Architecture, applications are developed by integration of existing services in order to reduce development cost and time. The approach, however, requires algorithms that select appropriate services out of available, alternative ones. The selection process may consider both optimalization requirements, such as maximalization of performance, and constraint requirements, such minimal security or maximum development...
-
Optimizing FSO networks resilient to adverse weather conditions by means of enhanced uncertainty sets
PublicationThis work deals with dimensioning of wireless mesh networks (WMN) composed of FSO (free space optics) links. Although FSO links realize broadband transmission at low cost, their drawback is sensitivity to adverse weather conditions causing transmission degradation on multiple links. Hence, designing such FSO networks requires an optimization model to find the cheapest configuration of link capacities that will be able to carry...
-
Telomere uncapping by common oxidative guanine lesions: Insights from atomistic models
PublicationOxidative damage to DNA is widely known to contribute to aging and disease. This relationship has been extensively studied for telomeres – structures that cap chromosome ends – due to their role in cell proliferation and senescence, and exceptional susceptibility to oxidation. Indeed, the repetitive telomeric DNA sequence contains the 5′-GGG-3′ motif that has the lowest ionization potential of all trinucleotides. Accordingly, experiments...
-
Types of Markov Fields and Tilings
PublicationThe method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to one-dimensional Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size m ≥ 2 can be viewed as models for multi-dimensional systems with local interactions. The locality of these interactions is represented...
-
Artificial Neural Networks for Prediction of Antibacterial Activity in Series of Imidazole Derivatives
Publication -
Advanced Assessment of the Endogenous Hormone Level as a Potential Biomarker of the Urogenital Tract Cancer
Publication -
High-throughput Evaluation of Lipophilicity and Acidity by New Gradient HPLC Methods
Publication -
The Osteopontin Tissue Level as a Breast Cancer Biomarker in Females After Mastectomy Measured by the Capillary Gel Electrophoresis Technique
Publication -
The Comparison Between the Calculated and HPLC-Predicted Lipophilicity Parameters for Selected Groups of Drugs
Publication -
Application of QSAR Analysis and Different Quantum Chemical Calculation Methods in Activity Evaluation of Selected Fluoroquinolones
Publication -
Activity Evaluation and Selection of Some Classes of Antibiotics with the use of Semi-Empirical Quantum Mechanics and Quantitative Structure- Activity Relationships Approach
Publication -
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Supervised-learning-based development of multi-bit RCS-reduced coding metasurfaces
PublicationCoding metasurfaces have been introduced as efficient tools allowing meticulous control over the electromagnetic (EM) scattering. One of their relevant application areas is radar cross section (RCS) reduction, which principally relies on the diffusion of impinging EM waves. Despite its significance, careful control of the scattering properties poses a serious challenge at the level of practical realization. This article is concerned...
-
Fluconazole resistant Candida auris clinical isolates have increased levels of cell wall chitin and increased susceptibility to a glucosamine-6-phosphate synthase inhibitor
PublicationIn 2009 Candida auris was first isolated as fungal pathogen of human disease from ear canal of a patient in Japan. In less than a decade, this pathogen has rapidly spread around the world and has now become a major health challenge that is of particular concern because many strains are resistant to multiple class of antifungal drugs. The lack of available antifungals and rapid increase of this fungal pathogen provides an incentive...
-
Normal-form preemption sequences for an open problem in scheduling theory
PublicationStructural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...