Wyszukiwarka
Filtry
wszystkich: 1358
-
Katalog
- Publikacje 1055 wyników po odfiltrowaniu
- Czasopisma 39 wyników po odfiltrowaniu
- Konferencje 35 wyników po odfiltrowaniu
- Osoby 46 wyników po odfiltrowaniu
- Wynalazki 1 wyników po odfiltrowaniu
- Projekty 7 wyników po odfiltrowaniu
- Kursy Online 21 wyników po odfiltrowaniu
- Wydarzenia 4 wyników po odfiltrowaniu
- Dane Badawcze 150 wyników po odfiltrowaniu
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: BIPARTITE GRAPHS
-
Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)
Dane BadawczeFor K3-e and Km-e graphs, the type coloring (K3-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3-e,Km-e) is the smallest...
-
Restrained differential of a graph
PublikacjaGiven a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood} of $v$ is defined to be $N(v)=\{u\in V(G) :\, uv\in E(G)\}$. The {external neighbourhood} of a set $S\subseteq V(G)$ is defined as $S_e=\left(\cup_{v\in S}N(v)\right)\setminus S$, while the \emph{restrained external neighbourhood} of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e\neq \varnothing\}$. The restrained differential of a graph $G$ is...
-
Graph security testing
PublikacjaSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Hat problem on a graph
PublikacjaThe topic of our paper is the hat problem. In that problem, each of n people is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
On the hat problem on a graph
PublikacjaThe topic of this paper is the hat problem in which each of n players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning....
-
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...
-
ON THE NON-LOCALITY OF TRIPARTITE NON-SINGALING BOXES EMERGING FROM WIRINGS
PublikacjaIt has been recently shown, that some of the tripartite boxes admittin g bilocal decom- position, lead to non-locality under wiring operation applied to t wo of the subsystems [R. Gallego et al. Physical Review Letters 109 , 070401 (2012)]. In the following, we study this phenomenon quantitatively. Basing on the known classes of bo xes closed un- der wirings, we introduce multipartite monotones which are count erparts of bipartite ones...
-
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublikacjaW 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.
-
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...
-
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.
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublikacjaPraca 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.
-
Modelling and analysis of beam/bar structure by application of bond graphs
PublikacjaThe 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...
-
Application of social relation graphs for early detection of transient spammers
PublikacjaWczesne 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...
-
Synchronization helps robots to detect black holes in directed graphs
PublikacjaPraca 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...
-
Average distance is submultiplicative and subadditive with respect to the strong product of graphs
PublikacjaWe 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.
-
Weakly convex and convex domination numbers of some products of graphs
PublikacjaIf $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}...
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublikacjaConsider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a...
-
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...
-
Workshop on Graph Theory
WydarzeniaThe Gdańsk Workshop on Graph Theory (GWGT) is an annual, informal workshop whose goal is to provide a forum for scientists to meet, present their work, interact, and establish collaborations in the field of Graph Theory
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublikacjaPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
Forwarding and optical indices of a graph
PublikacjaW 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.
-
Graph models of clos networks
Publikacja...
-
Fast Collaborative Graph Exploration
PublikacjaWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Interval incidence graph coloring
PublikacjaIn 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...
-
Zgred - Zgred Graph Editor
PublikacjaThe paper presents a graph editor that was developed as a supplementary tool for the Koala graph library. We discuss its requirements, design choices and main ideas behind the implementation. The later part of the paper is meant to be a brief user manual, as we go through the functionality provided by the editor
-
On a Recurrence Arising in Graph Compression
PublikacjaIn a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability p) or the right subtree (with probability 1p). A new node is created as long as...
-
Fast collaborative graph exploration
PublikacjaWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Mixed graph edge coloring
PublikacjaW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
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...
-
Parallel scheduling by graph ranking
PublikacjaNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...
-
A construction for the hat problem on a directed graph
PublikacjaA team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...
-
JOURNAL OF MOLECULAR GRAPHICS & MODELLING
Czasopisma -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publikacja -
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publikacja -
Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Publikacja -
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Modelling of distributed-lumped parameter systems by application of modal bond graphs.
PublikacjaZastosowano metodę transmitancji układów o parametrach rozłożonych oraz dekompozycję modalną do modelowania wybranych układów dynamicznych. Zaproponowane podejście pozwala otrzymać dokładne modele niskiego rzędu w postaci grafów wiązań.
-
Modelling electrical machines using bond graphs for mechatronics system applications.
PublikacjaW artykule przedstawiono modelowanie maszyn elektrycznych metodą grafów wiązań dla potrzeb mechatroniki. Omówiono ogólne założenia modelowania maszyn elektrycznych w ujęciu grafów wiązań, bazującego na modelach wzorcowego sprzężenia transformatorowego i elektromechanicznego. Wykorzystując modele tych sprzężeń przedstawiono w ujęciu grafów wiązań model maszyny indukcyjnej w układzie współrzędnych naturalnych stojana. Model opracowano...
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Equitable coloring of graphs. Recent theoretical results and new practical algorithms
PublikacjaIn this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublikacjaW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
All graphs with restrained domination number three less than their order
PublikacjaW pracy opisana jest rodzina wszystkich grafów, dla których liczbadominowania zewnętrznego jest o trzy mniejsza od ich rzędu.
-
All graphs with paired-domination number two less than their order
PublikacjaLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...
-
Unicyclic graphs with equal total and total outer-connected domination numbers
PublikacjaLet G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...
-
Spam classification methods besed on users e-mail communication graphs
PublikacjaW artykule poddano analizie grafy zbudowane w oparciu o logi serwerów pocztowych. Węzły grafów reprezentują nadawców i odbiorców wiadomości e-mail natomiast krawędzie przedstawiają procesy wymiany wiadomości e-mail. Analiza grafów pozwala na znalezienie korelacji pomiędzy topologią grafów a relacjami pomiędzy użytkownikami serwisu pocztowego. W oparciu o te relacje zaproponowano algorytm klasyfikujący wymieniane wiadomości e-mail...
-
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publikacja -
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublikacjaIn 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...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaWe 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.
-
An O ( n log n ) algorithm for finding edge span of cacti
PublikacjaLet 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...
-
Joanna Raczek dr inż.
OsobyWykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i Telekomunikacji,...