Wyniki wyszukiwania dla: SCHEDULING BIPARTITE GRAPH - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: SCHEDULING BIPARTITE GRAPH

Filtry

wszystkich: 545
wybranych: 432

wyczyść wszystkie filtry


Filtry wybranego katalogu

  • Kategoria

  • Rok

  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Wyniki wyszukiwania dla: SCHEDULING BIPARTITE GRAPH

  • Parallel scheduling by graph ranking

    Publikacja

    - Rok 2006

    Nr 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...

  • Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs

    Publikacja

    - Rok 2022

    The 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines

    Publikacja

    In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments

    We consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard,...

    Pełny tekst do pobrania w portalu

  • Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

    The problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...

    Pełny tekst do pobrania w portalu

  • Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms

    Publikacja

    - ARTIFICIAL INTELLIGENCE - Rok 2022

    In this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

    Publikacja

    - Rok 2008

    W 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)$.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

    The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...

    Pełny tekst do pobrania w portalu

  • A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

    We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...

    Pełny tekst do pobrania w portalu

  • Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees

    An edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Chromatic cost coloring of weighted bipartite graphs

    Given 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4

    In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...

    Pełny tekst do pobrania w portalu

  • Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2018

    We consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.

    Pełny tekst do pobrania w portalu

  • Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

    In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...

    Pełny tekst do pobrania w portalu

  • No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs

    In 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...

    Pełny tekst do pobrania w portalu

  • Total Completion Time Minimization for Scheduling with Incompatibility Cliques

    Publikacja

    - Rok 2021

    This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Approximation algorithms for job scheduling with block-type conflict graphs

    Publikacja

    - COMPUTERS & OPERATIONS RESEARCH - Rok 2024

    The 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Bipartite theory of graphs: outer-independent domination

    Publikacja

    - NATIONAL ACADEMY SCIENCE LETTERS-INDIA - Rok 2015

    Let $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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

    Publikacja

    - NEW JOURNAL OF PHYSICS - Rok 2016

    We study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scheduling of compatible jobs on parallel machines

    Publikacja

    - Rok 2021

    The dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...

  • Progress on Roman and Weakly Connected Roman Graphs

    Publikacja

    - Mathematics - Rok 2021

    A 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)....

    Pełny tekst do pobrania w portalu

  • Dynamic coloring of graphs

    Publikacja

    - FUNDAMENTA INFORMATICAE - Rok 2012

    Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...

  • Domination subdivision and domination multisubdivision numbers of graphs

    The 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...

    Pełny tekst do pobrania w portalu

  • The Backbone Coloring Problem for Bipartite Backbones

    Let G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • A construction for the hat problem on a directed graph

    Publikacja

    A 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Paired domination versus domination and packing number in graphs

    Publikacja

    Given 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...

    Pełny tekst do pobrania w portalu

  • Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph

    Publikacja
    • M. Lemańska
    • J. A. RODRíGUEZ-VELáZQUEZ
    • R. Trujillo-Rasua

    - FUNDAMENTA INFORMATICAE - Rok 2017

    A vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability

    This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Paired domination subdivision and multisubdivision numbers of graphs

    The 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...

    Pełny tekst do pobrania w portalu

  • Edge coloring of graphs of signed class 1 and 2

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2023

    Recently, 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Hat problem on odd cycles

    The topic is the hat problem in which each of n players is randomly 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 a win. In this version every player can...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Global defensive sets in graphs

    In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • An O ( n log n ) algorithm for finding edge span of cacti

    Let 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...

    Pełny tekst do pobrania w portalu

  • The hat problem on a union of disjoint graphs

    The topic is the hat problem in which each of n players is randomly 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. In this version every player...

    Pełny tekst do pobrania w portalu

  • On a matching distance between rooted phylogenetic trees

    The Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...

    Pełny tekst do pobrania w portalu

  • Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions

    Publikacja

    - JOURNAL OF COMPUTATIONAL BIOLOGY - Rok 2017

    Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Optimal edge-coloring with edge rate constraints

    Publikacja

    - NETWORKS - Rok 2013

    We 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....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Rearrangeability in multicast Clos networks is NP-complete

    Publikacja

    Przestrajalność 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Restricted open shop scheduling

    In the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • KernelHive: a new workflow-based framework for multilevel high performance computing using clusters and workstations with CPUs and GPUs

    The paper presents a new open-source framework called KernelHive for multilevel parallelization of computations among various clusters, cluster nodes, and finally, among both CPUs and GPUs for a particular application. An application is modeled as an acyclic directed graph with a possibility to run nodes in parallel and automatic expansion of nodes (called node unrolling) depending on the number of computation units available....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Shared processor scheduling

    Publikacja

    - JOURNAL OF SCHEDULING - Rok 2018

    We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class...

    Pełny tekst do pobrania w portalu

  • Restrained differential of a graph

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2023

    Given 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...

    Pełny tekst do pobrania w portalu

  • Interval incidence coloring of bipartite graphs

    In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...

    Pełny tekst do pobrania w portalu

  • Normal-form preemption sequences for an open problem in scheduling theory

    Publikacja

    - JOURNAL OF SCHEDULING - Rok 2016

    Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Graph classes generated by Mycielskians

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2020

    In 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...

    Pełny tekst do pobrania w portalu

  • TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2015

    The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msd_t (G) of a graph G and we show that for any connected graph G of order at least two, msd_t (G) ≤ 3. We show that for trees the total domination...

    Pełny tekst do pobrania w portalu

  • On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

    In 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.

    Pełny tekst do pobrania w portalu

  • EvOLAP Graph – Evolution and OLAP-Aware Graph Data Model

    Publikacja

    - Rok 2018

    The objective of this paper is to propose a graph model that would be suitable for providing OLAP features on graph databases. The included features allow for a multidimensional and multilevel view on data and support analytical queries on operational and historical graph data. In contrast to many existing approaches tailored for static graphs, the paper addresses the issue for the changing graph schema. The model, named Evolution...

    Pełny tekst do pobrania w portalu

  • Shared multi-processor scheduling

    Publikacja

    We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job’s completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Relations between the domination parameters and the chromatic index of a graph

    In this paper we show bounds for the sum and the product of the domination parameters and the chromatic index of a graph. We alsopresent some families of graphs for which these bounds are achieved.

    Pełny tekst do pobrania w portalu