DISCRETE APPLIED MATHEMATICS - Czasopismo - MOST Wiedzy

Wyszukiwarka

Discrete applied mathematics

SHERPA RoMEO status:

Zielony Pomoc
Pre-print
wersja autorska artykułu przed recenzją
Post-print
wersja autorska artykułu po recenzji

Tabela statusów SHERPA RoMEO

Tabela statusów SHERPA RoMEO
SHERPA RoMEO kolor Polityka archiwizacji
Zielony można archiwizować pre-printy i post-printy lub wersję wydawcy
Niebieski can archive post-prints
Żółty można archiwizować pre-printy
Biały nie można archiwizować żadnych materiałów
Szary brak danych

ISSN: 0166-218X

Współczynnik Impact Factor

Zaloguj się aby zobaczyć Współczynnik Impact Factor dla tego czasopisma

Weryfikacja:
Politechnika Gdańska

Punkty Ministerialne

Punkty Ministerialne
Lista Rok Punkty
A 2017 25
A 2016 25
A 2015 25
A 2014 25
A 2013 25
A 2011 25
A 2008 20

Filtry

wszystkich: 24

  • Kategoria
  • Rok

Katalog Czasopism

2019
  • Global edge alliances in graphs

    In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

    Pełny tekst w serwisie zewnętrznym

2018
2016
2015
  • Interval incidence graph coloring

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

    Pełny tekst w serwisie zewnętrznym

  • New potential functions for greedy independence and coloring
    Publikacja

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

    Pełny tekst w serwisie zewnętrznym

  • The computational complexity of the backbone coloring problem for planar graphs with connected backbones

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

    Pełny tekst w serwisie zewnętrznym

2014
  • Bondage number of grid graphs

    The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

    Pełny tekst w serwisie zewnętrznym

  • 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 w serwisie zewnętrznym

  • On the partition dimension of trees
    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2014

    Given an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...

    Pełny tekst w serwisie zewnętrznym

2013
  • Three-fast-searchable graphs
    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2013

    In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...

    Pełny tekst w serwisie zewnętrznym

2012
  • On the size of identifying codes in triangle-free graphs
    Publikacja

    - DISCRETE APPLIED MATHEMATICS - 2012

    In an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...

    Pełny tekst w serwisie zewnętrznym

2011
2010
2009
  • 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 w serwisie zewnętrznym

  • A note on the strength and minimum color sum of bipartite graphs

    Siłą 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.

    Pełny tekst w serwisie zewnętrznym

  • Approximating the maximum 2- and 3-edge-colorable subgraph problems

    Dla ustalonej wartości parametru k>=2, problem maksymalnego podgrafu krawędziowo k-kolorowalnego polega na wskazaniu k rozłącznych skojarzeń w grafie prostym, a kryterium optymalizacji jest maksymalizacja całkowitej liczby użytych krawędzi. W pracy podano algorytmy 5/6- i 4/5-przybliżone odpowiednio dla przypadków k=2 i k=3, poprawiając wyniki znane z literatury.

    Pełny tekst w serwisie zewnętrznym

  • Forwarding and optical indices of a graph

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

    Pełny tekst w serwisie zewnętrznym

  • Total outer-connected domination numbers of trees

    Niech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...

    Pełny tekst w serwisie zewnętrznym

2008
  • Edge ranking and searching in partial orders

    Artykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla...

    Pełny tekst w serwisie zewnętrznym

2007
  • Easy and hard instances of arc ranking in directed graphs

    Artykuł 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...

2003

wyświetlono 59 razy