Wyszukiwarka
Filtry
wszystkich: 444
wybranych: 332
-
Katalog
- Publikacje 332 wyników po odfiltrowaniu
- Czasopisma 5 wyników po odfiltrowaniu
- Konferencje 18 wyników po odfiltrowaniu
- Osoby 4 wyników po odfiltrowaniu
- Aparatura Badawcza 1 wyników po odfiltrowaniu
- Kursy Online 6 wyników po odfiltrowaniu
- Wydarzenia 1 wyników po odfiltrowaniu
- Dane Badawcze 77 wyników po odfiltrowaniu
Filtry wybranego katalogu
Wyniki wyszukiwania dla: DIGRAPH
-
On-line ranking of split graphs
PublikacjaA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
A NOTE ON ON-LINE RAMSEY NUMBERS FOR QUADRILATERALS
PublikacjaWe consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder’s goal is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \widetilde{r}(H) of...
-
Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios
PublikacjaThe problem of identifying measurement scenarios capable of revealing state-independent contextuality in a given Hilbert space dimension is considered. We begin by showing that for any given dimension d and any measurement scenario consisting of projective measurements, (i) the measure of contextuality of a quantum state is entirely determined by its spectrum, so that pure and maximally mixed states represent the two extremes...
-
Bounds on the cover time of parallel rotor walks
PublikacjaThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...
-
Wordventure - cooperative wordnet editor. Architecture for lexical semantic aquisition
PublikacjaThis article presents architecture for acquiring lexical semanticsin a collaborative approach paradigm. The system enablesfunctionality for editing semantic networks in a wikipedia-like style. The core of the system is a user-friendly interface based on interactive graph navigation.It has been used for semantic network presentation,and brings simultaneously modification functionality.
-
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...
-
WordVenture - COOPERATIVE WordNet EDITOR Architecture for Lexical Semantic Acquisition
PublikacjaThis article presents architecture for acquiring lexical semantics in a collaborative approach paradigm. The system enables functionality for editing semantic networks in a wikipedia-like style. The core of the system is a user-friendly interface based on interactive graph navigation. It has been used for semantic network presentation, and brings simultaneously modification functionality.
-
Distributed NVRAM Cache – Optimization and Evaluation with Power of Adjacency Matrix
PublikacjaIn this paper we build on our previously proposed MPI I/O NVRAM distributed cache for high performance computing. In each cluster node it incorporates NVRAMs which are used as an intermediate cache layer between an application and a file for fast read/write operations supported through wrappers of MPI I/O functions. In this paper we propose optimizations of the solution including handling of write requests with a synchronous mode,...
-
Turán numbers for odd wheels
PublikacjaThe Turán number ex(n,G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W_n is a graph on n vertices obtained from a C_{n−1} by adding one vertex w and making w adjacent to all vertices of the C_{n−1}. We obtain two exact values for small wheels: ex(n,W_5)=\lfloor n^2/4+n/2\rfloor, ex(n,W_7)=\lfloor n^2/4+n/2+1 \rfloor. Given that ex(n,W_6) is already known, this...
-
A Systematic Search for New Coupling Schemes of Cross-Coupled Resonator Bandpass Filters
PublikacjaIn this paper, a systematic approach to an extensive search for topologies of cross-coupled filters with generalized Chebyshev response is presented. The technique applies graph theory to find unique, nonisomorphic filter configurations, and tests whether a specific frequency response can be realized in a given set of topologies. The results of the search are then stored in a database of possible filter configurations.
-
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.
-
New potential functions for greedy independence and coloring
PublikacjaA 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...
-
Parity vertex colouring of graphs
PublikacjaA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Optimal edge-coloring with edge rate constraints
PublikacjaWe 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....
-
Network Approach to Increments of RR-intervals for Visualization of Dynamics of Cardiac Regulation
PublikacjaThe transition network for RR -increments is pre- sented in a directed and weighted graph, with vertices represent- ing RR -increments and edges corresponding to the order in a sequence of increments. The adjacency matrix and the transition matrix of this network provide a graphical tool which could be useful in the assessment of cardiac regulation. As an example, the method is applied in detecting differences between diurnal activity...
-
A note on mixed tree coloring
PublikacjaZaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].
-
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).
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm.
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
Convex universal fixers
PublikacjaPraca dotyczy dominowania wypukłego w grafach pryzmowych.
-
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.
-
Some variations of perfect graphs
PublikacjaWe consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...
-
On-line P-coloring of graphs
PublikacjaFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publikacja -
Weakly connected domination subdivision numbers
PublikacjaLiczba podziału krawędzi dla dominowania słabo spójnego to najmniejsza liczba krawędzi jaką należy podzielić, aby wzrosła liczba dominowania słabo wypukłego. W pracy przedstawione są własności liczby podziału krawędzi dla dominowania słabo spójnego dla różnych grafów.
-
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.
-
Trees with equal restrained domination and total restrained domination numbers
PublikacjaW publikacji scharakteryzowano wszystkie drzewa, w których liczby dominowania powściągniętego oraz podwójnie totalnego są sobie równe.
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublikacjaW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
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.
-
Total outer-connected domination in trees
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego w grafach oraz scharakteryzowano wszystkie drzewa osiągające to ograniczenie.
-
T-colorings, divisibility and circular chromatic number
PublikacjaLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
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.
-
Recognition, understanding and aestheticization of freehand drawing flowcharts
PublikacjaIn this paper a concept of FCA, a system for recognizing, understanding and aestheticization of freehand drawing flow charts is described. The system is based on a proposed by the author FlowGram graph grammar describing flow charts drawing. An open format FlowChartML for flow charts description is also proposed. The aestheticization criterion is formulated that allows for automatic beautification of flow charts. First experiments...
-
On zero-error codes produced by greedy algorithms
PublikacjaWe 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.
-
Separability Assessment of Selected Types of Vehicle-Associated Noise
PublikacjaMusic Information Retrieval (MIR) area as well as development of speech and environmental information recognition techniques brought various tools in-tended for recognizing low-level features of acoustic signals based on a set of calculated parameters. In this study, the MIRtoolbox MATLAB tool, designed for music parameter extraction, is used to obtain a vector of parameters to check whether they are suitable for separation of...
-
Complexity Issues on of Secondary Domination Number
PublikacjaIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
The complexity of minimum-length path decompositions
PublikacjaWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublikacjaIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublikacjaSmart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....
-
Cooperative Word Net Editor for Lexical Semantic Acquisition
PublikacjaThe article describes an approach for building Word Net semantic dictionary in a collaborative approach paradigm. The presented system system enables functionality for gathering lexical data in a Wikipedia-like style. The core of the system is a user-friendly interface based on component for interactive graph navigation. The component has been used for Word Net semantic network presentation on web page, and it brings functionalities...
-
Generalized Gradient Equivariant Multivalued Maps, Approximation and Degree
PublikacjaConsider the Euclidean space Rn with the orthogonal action of a compact Lie group G. We prove that a locally Lipschitz G-invariant mapping f from Rn to R can be uniformly approximated by G-invariant smooth mappings g in such a way that the gradient of g is a graph approximation of Clarke’s generalized gradient of f . This result enables a proper development of equivariant gradient degree theory for a class of set-valued gradient...
-
Proposal of a method for effective tasks distribution in the execution of compolex problems
PublikacjaAn access to a great number of various services allows for decomposition of complex problems into smaller and less complex tasks. Those tasks can be presented in a form of a dependency graph. This paper shows an idea of executing such a problem using cooperating autonomous agents. Main focus of this work is cooperation covering effective tasks distribution among executors. This paper presents an algorithm for dynamic executor selection...
-
Reliability of production machines in the bakery industry – theoretical and practical issues
PublikacjaThe aim of the article is to present probabilistic models, which were then used to analyze the reliability of production machines in the baking industry. The author conducted research in the period from January 2, 2016 to December 31, 2018 regarding the measurement of reliability of a traditional production system based on a probabilistic concept. Due to the limited scope of the article, reliability calculations for a set of thermo-oil...
-
ProSIL Software for functional saferty management in life cycle = Aplikacja ProSIL do zarządzania bezpieczeństwem funkcjonalnym w cyklu życia
PublikacjaIn the paper the ProSIL software to aid the functional safety management is presented. The software consists of three modules to aid: determination of the required SIL level (ProSILen), veryfication of the SIL level (ProSILver). In the aplication the method of the calibrated risk graph to determine the required safety integrity level SIL for defined safety instrumented functions is applied. The methods concerning functional safety...
-
Port-Based Modelling of Distributed-Lumped Parameter Systems
PublikacjaThere in the paper is presented an uniform, port-based approach to modelling of both lumped and distributed parameter systems. Port-based model of the distributed system has been defined by application of bond graph methodology and distributed transfer function method (DTFM). The approach proposed combines versatility of port-based modelling and accuracy of distributed transfer function method. The concise representation of lumped-distributed...
-
Polyhedral Ramsey Numbers
PublikacjaGiven two polygons or polyhedrons P1 and P2, we can transform these figures to graphs G1 and G2, respectively. The polyhedral Ramsey number Rp(G1,G2) is the smallest integer n such that every graph, which represents polyhedron on n vertices either contains a copy of G1 or its complement contains a copy of G2. Using a computer search together with some theoretical results we have established some polyhedral Ramsey numbers, for example...
-
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...
-
Study of the Flow Dynamics of Surface Water Masses in the Area of the Coastal Gulf of Gdansk
PublikacjaThe paper describes two methods of predicting the movement of small objects with surface water masses. One of the methods uses graph theory to describe the motion of water masses in port docks. The results of this study were compared to a simulation using the hydrodynamic numerical model M3D. The results obtained in a virtual environment were related to the experiments in the real world. In the coastal area of the Gulf of Gdansk,...
-
Rearrangeability in multicast Clos networks is NP-complete
PublikacjaPrzestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...
-
Certified domination
PublikacjaImagine 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...