Filtry
wszystkich: 842
wybranych: 709
-
Katalog
- Publikacje 709 wyników po odfiltrowaniu
- Czasopisma 14 wyników po odfiltrowaniu
- Konferencje 19 wyników po odfiltrowaniu
- Osoby 10 wyników po odfiltrowaniu
- Wynalazki 1 wyników po odfiltrowaniu
- Projekty 1 wyników po odfiltrowaniu
- Kursy Online 4 wyników po odfiltrowaniu
- Wydarzenia 2 wyników po odfiltrowaniu
- Dane Badawcze 82 wyników po odfiltrowaniu
Filtry wybranego katalogu
Wyniki wyszukiwania dla: GRAPH DECONTAMINATION
-
Bipartite theory of graphs: outer-independent domination
PublikacjaLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
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.
-
On the super domination number of lexicographic product graphs
PublikacjaThe 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...
-
Graphs with equal domination and certified domination numbers
PublikacjaA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
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...
-
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)....
-
Domination subdivision and domination multisubdivision numbers of graphs
PublikacjaThe domination subdivision number sd(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 domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
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.
-
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...
-
Identification of the Contamination Source Location in the Drinking Water Distribution System Based on the Neural Network Classifier
PublikacjaThe contamination ingression to the Water Distribution System (WDS) may have a major impact on the drinking water consumers health. In the case of the WDS contamination the data from the water quality sensors may be efficiently used for the appropriate disaster management. In this paper the methodology based on the Learning Vector Quantization (LVQ) neural network classifier for the identification of the contamination source location...
-
Contamination of runoff waters from roads with high traffic intensity in the urban region of Gdańsk, Poland
PublikacjaW ramach pracy prowadzone były badania zanieczyszczeń w próbkach wód spływnych z arterii komunikacyjnych. Próbki pobierano z sześciu stałych punktów zlokalizowanych wzdłuż szlaku komunikacyjnego prowadzącego z Redy do Gdańska (z miejsc o dużym natężeniu ruchu pojazdów) oraz z ulicy M. Buczka w Redzie (o mniejszym natężeniu ruchu). Próbki pobierane były przez okres dwóch miesięcy (okres deszczów jesiennych: 24.10 - 18.12.2000) oraz...
-
Zanieczyszczenie wód gruntowych odciekami ze składowiska odpadów. Groundwater contamination by the leakeage from the landfill.
PublikacjaJednym z poważnych zagrożeń środowiska są stare składowiska odpadów z uwagi na ich nieodpowiednią lokalizację bądź zabezpieczenia nie spełniające obecnie obowiązujących wymagań i unormowań prawnych. Sytuację taką zaobserwowano na analizowanym obszarze badawczym. Zalegające na tym terenie odpady nie są izolowane od warstwy wodonośnej, w związku z czym wody opadowe filtrujące przez warstwę odpadów powodują zanieczyszczenie wód gruntowych...
-
Trace Metal Contamination of Bottom Sediments: A Review of Assessment Measures and Geochemical Background Determination Methods
PublikacjaThis paper provides an overview of different methods of assessing the trace metal (TM) contamination status of sediments affected by anthropogenic interference. The geochemical background determination methods are also described. A total of 25 papers covering rivers, lakes, and retention tanks sediments in areas subjected to anthropogenic pressure from the last three years (2019, 2020, and 2021) were analysed to support our examination...
-
CAUSALITY IN MODELS OF THERMAL PROCESSES IN SHIP ENGINE ROOMS WITH THE USE OF BOND GRAPH (BG) METHOD
PublikacjaWith a single approach to modeling elements of different physical nature, the method of Bond Graph (BG) is particularly well suited for modeling energy systems consisting of mechanical, thermal, electrical and hydraulic elements that operate in the power system engine room. The paper refers to the earlier presented new concept of thermal process modeling using the BG method. The authors own suggestions for determining causality...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
The complexity of the T-coloring problem for graphs with small degree
Publikacja -
Some results concerning the complexity of restricted colorings of graphs
Publikacja -
Edge-chromatic sum of trees and bounded cyclicity graphs
Publikacja -
A note on compact and compact circular edge-colorings of graphs
PublikacjaW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Graphs with equal domination and 2-distance domination numbers
PublikacjaW publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.
-
Packing [1,Delta]-factors in graphs of small degree
PublikacjaRozważ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 approximation algorithm for maximum P3-packing in subcubic graphs
PublikacjaW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
Early detection of imminent threats in social relation graphs
PublikacjaWczesne wykrywanie zagrożeń i anomalii w sieciach społecznych jest dziś prawdziwym wyzwaniem. Ludzie w realnym świecie tworzą wiele złożonych relacji społecznych, które mogą być przedstawione za pomocą grafów, w których węzły reprezentują aktorów (pojedyncze osoby lub organizacje) a krawędzie wskazują na powiązania pomiędzy nimi. Analiza nieustannie zmieniających się relacji pomiędzy aktorami może wskazać konkretne nadciągające...
-
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł 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...
-
A note on the strength and minimum color sum of bipartite graphs
PublikacjaSiłą 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.
-
Total domination in versus paired-domination in regular graphs
PublikacjaA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...
-
The paired-domination and the upper paired-domination numbers of graphs
PublikacjaIn this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.
-
Metaheurystyki sztucznej inteligencji w wybranych grach komputerowych
PublikacjaW pracy omówiono trzy metaheurystyki sztucznej inteligencji, które mogą stać się źródłem inspiracji dla projektantów gier komputerowych. Pokazano, w jaki sposób zastosowano algorytm mrówkowy, algorytm genetyczny i algorytm tabu search w grach komputerowych zaprojektowanych przez studentów Politechniki Gdańskiej. W szczególności, odniesiono się do problematyki wyznaczania trajektorii przemieszczających się obiektów...
-
The complexity of the T-coloring problem for graphs with small degree.
PublikacjaW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Domination numbers in graphs with removed edge or set of edges
PublikacjaW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublikacjaIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
Ramsey numbers for triangles versus almost-complete graphs.
PublikacjaPokazano, że w każdym krawędziowym pokolorowaniu dwoma kolorami grafu pełnego o 38 wierzchołkach występuje trójkąt w pierwszym kolorze lub podgraf izomorficzny z K_10 - e w drugim kolorze. Stąd otrzymujemy górne oszacowanie R(K_3, K_10 - e) <= 38. Przedstawiamy także pokolorowanie krawędziowe grafu K_36, którego istnienie dowodzi, że R(K_3, K_10 - e) >= 37.
-
Processing of musical metadata employing Pawlak's flow graphs.
PublikacjaW artykule przedstawiono problemy wyszukiwania informacji muzycznej. W eksperymentach posłużono się meta opisem oraz wykorzystano metodę grafów przepływowych Pawlaka. Opisano skonstruowaną bazę nagrań muzycznych. Słowa kluczowe: meta opis, wyszukiwanie informacji muzycznej, baza danych muzycznych
-
Music Archive Metadata Processing Based on Flow Graphs.
PublikacjaW referacie zaproponowano metodykę wyszukiwania informacji muzycznej w bazach internetowych w oparciu o meta opis. Skonstruowany algorytm wykorzystuje grafy przepływowe Pawlaka.
-
Optimal backbone coloring of split graphs with matching backbones
PublikacjaFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
PublikacjaWe study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...
-
Graphs with isolation number equal to one third of the order
PublikacjaA set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by \iota(G) , is the minimum cardinality of an isolating set of G. It is known that \iota(G) \leq n/3 , if G is a connected graph of order n, , distinct from C_5 . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number...
-
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.
-
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”,...
-
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...
-
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...
-
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...
-
Identification of the featured-element in fine road dust of cities with coal contamination by geochemical investigation and isotopic monitoring
Publikacja -
Occurrence, contamination evaluation and health risks of trace metals within soil, sediments and tailings in southern Tunisia
Publikacja -
Biological responses to environmental contamination. How can metal pollution impact signal honesty in avian species?
PublikacjaEnvironmental pollution, for example with metals, can significantly affect the ecosystem balance leading to severe changes. Biologically active pigments are relevant for the appearance and condition of birds. Melanin and carotenoid particles are the most frequently deposited pigments in avian integument. They are responsible for the majority of colors of bird plumage. The phenotypic expression can be affected by metal contamination....
-
Contamination of Runoff Water at Gdańsk Airport (Poland) by Polycyclic Aromatic Hydrocarbons (PAHs) and Polychlorinated Biphenyls (PCBs)
PublikacjaAirport runoff can contain high concentrations of various pollutants, in particular polycyclic aromatic hydrocarbons (PAHs) and polychlorinated biphenyls (PCBs), the environmental levels of which have to be monitored. Airport runoff water samples, collected at the Gdańsk-Rębiechowo Airport from 2008 to 2009, were analysed for PAHs and PCBs by gas chromatography. The aromatic fractions were separated by liquid-liquid extraction...
-
First evaluation of wastewater discharge influence on marine water contamination in the vicinity of Arctowski Station (Maritime Antarctica)
PublikacjaIn Antarctica,waste is generatedmainly during scientific research programmes and related logistics. In this study, the impact ofwastewater on the western shore of Admiralty Baywas investigated during austral summer in 2017 and 2019. A range of physicochemical parameters and the presence of selected trace metals, formaldehyde and different groups of surfactants were determined in wastewater coming from Arctowski Station and in nearby coastal...
-
Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction
PublikacjaIonic liquids (ILs) provide a promising solution in many industrial applications, such as solvents, absorbents, electrolytes, catalysts, lubricants, and many others. However, due to the enormous variety of their structures, uncovering or designing those with optimal attributes requires expensive and exhaustive simulations and experiments. For these reasons, searching for an efficient theoretical tool for finding the relationship...
-
Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
PublikacjaGiven two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...