Filters
total: 898
-
Catalog
Search results for: CATEGORY GRAPH
-
Graphs hard-to-process for greedy algorithm MIN
PublicationWe 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
PublicationThe 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...
-
Graphs with convex domination number close to their order
PublicationW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublicationReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
A collection of directed graphs for the minimum cycle mean weight computation
Open Research DataThis dataset contains definitions of the 16 directed graphs with weighted edges that were described in the following paper: Paweł Pilarczyk, A space-efficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349--355, DOI: 10.22436/jmcs.020.04.08, URL: http://dx.doi.org/10.22436/jmcs.020.04.08 These...
-
CAUSALITY IN MODELS OF THERMAL PROCESSES IN SHIP ENGINE ROOMS WITH THE USE OF BOND GRAPH (BG) METHOD
PublicationWith 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...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe 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”,...
-
Block graphs with large paired domination multisubdivision number
PublicationThe 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.
-
The complexity of the T-coloring problem for graphs with small degree
Publication -
Some results concerning the complexity of restricted colorings of graphs
Publication -
Edge-chromatic sum of trees and bounded cyclicity graphs
Publication -
The maximum edge-disjoint paths problem in complete graphs
PublicationRozważ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...
-
A note on compact and compact circular edge-colorings of graphs
PublicationW 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...
-
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 approximation algorithm for maximum P3-packing in subcubic graphs
PublicationW 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).
-
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...
-
Early detection of imminent threats in social relation graphs
PublicationWczesne 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...
-
The circular chromatic index of some class 2 graphs
PublicationW 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.
-
Processing of musical metadata employing Pawlak's flow graphs.
PublicationW 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.
PublicationW referacie zaproponowano metodykę wyszukiwania informacji muzycznej w bazach internetowych w oparciu o meta opis. Skonstruowany algorytm wykorzystuje grafy przepływowe Pawlaka.
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Ramsey numbers for triangles versus almost-complete graphs.
PublicationPokazano, ż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.
-
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...
-
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.
-
The paired-domination and the upper paired-domination numbers of graphs
PublicationIn 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
PublicationW 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...
-
Graphs with equal domination and 2-distance domination numbers
PublicationW 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.
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor 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
PublicationWe 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...
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublicationIn 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...
-
Graphs with isolation number equal to one third of the order
PublicationA 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...
-
Total domination in versus paired-domination in regular graphs
PublicationA 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...
-
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...
-
Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublicationThe 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...
-
Domination numbers in graphs with removed edge or set of edges
PublicationW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
Analysis of measurement uncertainty for contact-less method used to measure the position of catenary contact wire, performed with the use of Monte Carlo method
PublicationCurrently the majority of main railway lines in Europe are electrified, and electric trains have the biggest share in the entire amount of rail transport. Reliability of electrified railways is closely related to the issue of supplying traction vehicles with energy. The problems connected with diagnostics of energy consumption node, namely the contact line and the current collector, are therefore of fundamental importance for maintaining...
-
Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction
PublicationIonic 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
PublicationGiven 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,...
-
Journal of Graph Algorithms and Applications
Journals -
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublicationW pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
-
Application of social relation graphs for early detection of transient spammers
PublicationWczesne wykrywanie społecznych zagrożeń i anomalii jest prawdziwym wyzwaniem w dzisiejszch, dynamicznych społeczeństwach. Ludzie tworzą skoplikowane relacje społeczne, które mogą być przedstawione za pomocą różnych typów grafów, których wierzchołki reprezentować mogą aktorów sieci (konkretne osoby lub organizacje) a krawędzie relacje pomiędzy nimi. Analiza tych dynamicznie zmieniających się relacji może wskazywać na niektóre nadciągające...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublicationPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
Average distance is submultiplicative and subadditive with respect to the strong product of graphs
PublicationWe show that the average distance is submultiplicative and subadditive on the set of non-trivial connected graphs with respect to the strong product. We also give an application of the above-mentioned result.
-
Synchronization helps robots to detect black holes in directed graphs
PublicationPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
Weakly convex and convex domination numbers of some products of graphs
PublicationIf $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...
-
Modelling and analysis of beam/bar structure by application of bond graphs
PublicationThe paper presents an uniform, port-based approach to modelling of beam/bar systems (trusses). Port-based model of such distributed parameter system has been defined by application of the bond graph methodology and the distributed transfer function method (DTFM). The proposed method of modelling enables to formulate input data for computer analysis by application of the DTFM. The constructed computational package enables the frequency...
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublicationThe problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...
-
Quantum strategies for rendezvous and domination tasks on graphs with mobile agents
PublicationThis 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...
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe 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.
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.