Search
Didn't find any results in this catalog!
But we have some results in other catalogs.Filters
total: 684
-
Catalog
Search results for: GRAPH PARTITIONING
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
Discussiones Mathematicae Graph Theory
Journals -
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
GRAPHS AND COMBINATORICS
Journals -
Partitioning total heart rate variability
Publication -
On-Line Partitioning for On-Line Scheduling with Resource Conflicts
PublicationWithin this paper, we consider the problem of on-line partitioning the sequence of jobs which are competing for non-sharable resources. As a result of partitioning we get the subsets of jobs that form separate instances of the on-line scheduling problem. The objective is to generate a partition into the minimum number of instances such that the response time of any job in each instance is bounded by a given constant. Our research...
-
Evolutionary Algorithm for Selecting Dynamic Signatures Partitioning Approach
PublicationIn the verification of identity, the aim is to increase effectiveness and reduce involvement of verified users. A good compromise between these issues is ensured by dynamic signature verification. The dynamic signature is represented by signals describing the position of the stylus in time. They can be used to determine the velocity or acceleration signal. Values of these signals can be analyzed, interpreted, selected, and compared....
-
Signature Partitioning Using Selected Population-Based Algorithms
PublicationDynamic signature is a biometric attribute which is commonly used for identity verification. Artificial intelligence methods, especially population-based algorithms (PBAs), can be very useful in the dynamic signature verification process. They are able to, among others, support selection of the most characteristic descriptors of the signature or perform signature partitioning. In this paper, we focus on creating the most characteristic...
-
Joanna Raczek dr inż.
PeopleEmployment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...