Search results for: discrete%20element%20method
-
On the deficiency of bipartite graphs
Publication -
A polynomial algorithm for finding T-span of generalized cacti
Publication -
A note on total reinforcement in graphs
PublicationIn this note we prove a conjecture and inprove some results presendet in a recent paper of N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202.
-
A station strategy to deter backoff attacks in IEEE 802.11 LANs
PublicationDla konstrukcji strategii zapobiegającej atakom na mechanizm odczekania w sieciach lokalnych IEEE 802.11 zastosowano wybór konfiguracji MAC sterowany przez liczniki etapów gry z losowymi wartościami początkowymi. Wykazano, że przy pewnych warunkach nałożonych na rozkady prawdopodobieństwa liczników standardowe ustawienia parametrów MAC stają się punktem doskonałej równowagi strategicznej.
-
Easy and hard instances of arc ranking in directed graphs
PublicationArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
Edge ranking and searching in partial orders
PublicationArtykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla...
-
Forwarding and optical indices of a graph
PublicationW pracy rozstrzygnięto dwa problemy dotyczące komunikacji wszyscy-do-wszystkich w grafach. Stwierdzono, że dla wersji skierowanej problemu parametry ''pi'' (maksymalne obciążenie krawędzi) i ''w'' (parametr chromatyczny) nie muszą być w ogólności sobie równe. Dla wersji nieskierowanej problemu pokazano, że wyznaczenie wartości zarówno ''pi'', jak i ''w'', jest w ogólności problemem NP-trudnym.
-
A note on the strength and minimum color sum of bipartite graphs
PublicationSiłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.
-
A note on the weakly convex and convex domination numbers of a torus
PublicationW pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.
-
On the partition dimension of trees
PublicationGiven an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
On the size of identifying codes in triangle-free graphs
PublicationIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
Equitable coloring of hypergraphs
PublicationA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Infinite chromatic games
PublicationIn 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...
-
Three-fast-searchable graphs
PublicationIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
Total outer-connected domination numbers of trees
PublicationNiech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...
-
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
Approximating the maximum 2- and 3-edge-colorable subgraph problems
PublicationDla ustalonej wartości parametru k>=2, problem maksymalnego podgrafu krawędziowo k-kolorowalnego polega na wskazaniu k rozłącznych skojarzeń w grafie prostym, a kryterium optymalizacji jest maksymalizacja całkowitej liczby użytych krawędzi. W pracy podano algorytmy 5/6- i 4/5-przybliżone odpowiednio dla przypadków k=2 i k=3, poprawiając wyniki znane z literatury.
-
New potential functions for greedy independence and coloring
PublicationA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
Bondage number of grid graphs
PublicationThe bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
On bipartization of cubic graphs by removal of an independent set
PublicationWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
PublicationWe consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Interval incidence coloring of bipartite graphs
PublicationIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
Interval incidence graph coloring
PublicationIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
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...
-
Comparative modeling of shear localization in granular bodies with FEM and DEM
PublicationThe intention of the paper is to compare the calculations of shear zones in granular bodies using two different approaches: a continuum and a discrete one. In the first case, the FEM based on a micro-polar hypoplastic constitutive law was used. In the second case, the DEM was taken advantage of, where contact moments were taken into account to model grain roughness. The comparative calculations were performed for a passive case...
-
A new open-source software developed for numerical simulations usingdiscrete modeling methods
PublicationThe purpose of this work is to present the development of an open-source software based on a discrete description of matter applied to study the behavior of geomaterials. This software uses Object Oriented Programming techniques, and its methodology design uses three different methods, which are the Discrete Element Method (DEM) [F. Donzé, S.A. Magnier, Formulation of a three-dimensional numerical model of brittle behavior, Geophys....
-
Myelodysplastic syndrome, NOS - Male, 65 - Tissue image [11290630017298681]
Open Research DataThis is the histopathological image of HEMATOPOIETIC AND RETICULOENDOTHELIAL SYSTEMS tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Myelodysplastic syndrome, NOS - Male, 65 - Tissue image [11290630017293141]
Open Research DataThis is the histopathological image of HEMATOPOIETIC AND RETICULOENDOTHELIAL SYSTEMS tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Towards Contactless, Hand Gestures-Based Control of Devices
PublicationGesture-based intuitive interactions with electronic devices can be an important part of smart home systems. In this paper, we adapt the contactless linear gesture sensor for the navigation of smart lighting system. Set of handled gestures allow to propose two methods of active light source selection, continuous dimming, and turning on and off based on discrete gestures. The average gesture recognition accuracy was 97.58% in the...
-
Comparison of noise reduction methods in radiometric correlation measurements of two-phase liquid-gas flows
PublicationTwo-phase liquid-gas flows occur frequently in the mining, energy, chemical, and petrochemical industries. One of non-contact methods used to analyse these flows is the gamma ray absorption method. However, the signals received from radiation detectors contain a significant stochastic noise, which makes them difficult to analyse. The article describes four methods of noise reduction in cross-correlation measurements of water-air...
-
Simulation model of IPMSM drive with rotor position estimator
PublicationThe paper presents a simulation model of electric drive consisting of: IPMSM motor, inverter and digital controller. The model was designed in Mathlab/Simulink. By modelling of the controller its discrete operation was taken into account in order to simulate precisely a specific sensorless control algorithm. A method for estimation of angular rotor position was proposed. Its mathematical algorithm was explained and errors were...
-
Curlicues generated by circle homeomorphisms
PublicationWe investigate the curves in the complex plane which are generated by sequences of real numbers being the lifts of the points on the orbit of an orientation preserving circle homeomorphism. Geometrical properties of these curves such as boundedness, superficiality, local discrete radius of curvature are linked with dynamical properties of the circle homeomorphism which generates them: rotation number and its continued fraction...
-
Numerical modeling of the combustion in a lab-scale pulverized-coal fired combustion chamber
PublicationThis work presents results of numerical modeling of the combustion process inside a lab-scale drop-tube chamber, designed to investigate the slagging properties of the flue ashes, created through the solid fuel firing. Interaction between turbulence and chemistry is accounted by use of probability density function (PDF). FLUENT inputs for non-premixed combustion chemistry modeling are defined. A discrete second phase of the coal...
-
Numerical modeling of the combustion in a lab-scale pulverized-coal fired combustion chamber
PublicationThis work presents results of numerical modeling of the combustion process inside a lab-scale drop-tube chamber, designed to investigate the slagging properties of the flue ashes, created through the solid fuel firing. Interaction between turbulence and chemistry is accounted by use of probability density function (PDF). FLUENT inputs for non-premixed combustion chemistry modeling are defined. A discrete second phase of the coal...
-
Mode choice modelling for urban areas
PublicationThe article presents the question of mode choice modelling in a four-stage travel modelling process. The article indicates limitations of currently used simplified methods of mode choice modelling and presents the possibility of using a more detailed approach that accounts for additional, statistically significant factors with the use of advanced mathematical tools, discrete choice models. A need has also been identified to include...
-
Numerical Issues and Approximated Models for the Diagnosis of Transmission Pipelines
PublicationThe chapter concerns numerical issues encountered when the pipeline flow process is modeled as a discrete-time state-space model. In particular, issues related to computational complexity and computability are discussed, i.e., simulation feasibility which is connected to the notions of singularity and stability of the model. These properties are critical if a diagnostic system is based on a discrete mathematical model of the flow...
-
Parameter and delay estimation of linear continuous-time systems
PublicationIn this paper the problem of on-line identification of non-stationary delay systems is considered. Dynamics of supervised industrial processes is described by ordinary differential equations. Discrete-time mechanization of their continuous-time representations is based on dedicated finite-horizon integrating filters. Least-squares and instrumental variable procedures implemented in recursive forms are applied for simultaneous identification...
-
On domination multisubdivision number of unicyclic graphs
PublicationThe paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...
-
ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (ACM/IEEE/SCS Workshop on Parallel and Distributed Simulation)
Conferences -
QoS Resource Reservation Mechanisms for Switched Optical Networks
PublicationThe paper regards the problem of resource reservation mechanisms for Quality of Service support in switched optical networks. The authors propose modifications and extensions for resources reservation strategy algorithms with resources pools, link capacity threshold and adaptive advance reservation approach. They examine proposed solutions in Automatically Switched Optical Network with Generalized Multi-Protocol Label Switching...
-
Influence analysis of selected parameters on the ASON/GMPLS control plane performance
PublicationThe paper regards the problem of ASON/GMPLS performance. The authors present influence analysis of selected parameters on the ASON/GMPLS control plane performance represented in mean Connection Set-up Time E(CST) and mean Connection Release Time E(CRT). The selected parameters are: offered traffic, request intensity and proportion of requests class. The influence analysis is performed with simulation method by using OMNeT++ discrete-event...
-
A new approach to active noise and vibration control - [Part II: unknown frequency case]
PublicationThis paper presents a new approach to rejection of complex-valued sinusoidal disturbances acting at the output of a discrete-time stable linear plant with unknown and possibly timevarying dynamics. It is assumed that both the instantaneous frequency of the sinusoidal disturbance and its amplitude may be slowly varying with time and that the output signal is contaminated with wideband measurement noise. It is not assumed that a...
-
On–line Parameter and Delay Estimation of Continuous–Time Dynamic Systems
PublicationThe problem of on-line identification of non-stationary delay systems is considered. The dynamics of supervised industrial processes are usually modeled by ordinary differential equations. Discrete-time mechanizations of continuous-time process models are implemented with the use of dedicated finite-horizon integrating filters. Least-squares and instrumental variable procedures mechanized in recursive forms are applied for simultaneous...
-
Parameter and delay estimation of linear continuous-time systems
PublicationIn this paper the problem of on-line identification of non-stationary delay systems is considered. Dynamics of supervised industrial processes is usually described by ordinary differential equations. Discrete-time mechanization of their continuous-time representations is based on dedicated finite-horizon integrating filters. Least-squares and instrumental variable procedures implemented in recursive forms are applied for simultaneous...