Katedra Algorytmów i Modelowania Systemów - Jednostki Administracyjne - MOST Wiedzy

Wyszukiwarka

Katedra Algorytmów i Modelowania Systemów

Filtry

wszystkich: 102

  • Kategoria
  • Rok
  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Katalog Publikacji

Rok 2024
Rok 2023
Rok 2022
  • Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
    Publikacja

    We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2021
  • An Efficient Noisy Binary Search in Graphs via Median Approximation
    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2021

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

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2019
Rok 2018
  • On domination multisubdivision number of unicyclic graphs
    Publikacja

    The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...

    Pełny tekst do pobrania w portalu

  • Total domination in versus paired-domination in regular graphs

    A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

    Pełny tekst do pobrania w portalu

  • Total Domination Versus Domination in Cubic Graphs
    Publikacja

    A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

    Pełny tekst do pobrania w portalu

Rok 2016
Rok 2015
Rok 2014
  • Some Progress on Total Bondage in Graphs
    Publikacja

    - GRAPHS AND COMBINATORICS - Rok 2014

    The total bondage number b_t(G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges E'⊆E(G) for which (1) G−E' has no isolated vertex, and (2) γ_t(G−E')>γ_t(G). We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number.

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2013
  • Relationship between semi- and fully-device-independent protocols
    Publikacja
    • H. Li
    • P. A. Mironowicz
    • M. Pawłowski
    • Z. Yin
    • Y. Wu
    • S. Wang
    • W. Chen
    • H. Hu
    • G. Guo
    • Z. Han

    - PHYSICAL REVIEW A - Rok 2013

    We study the relation between semi and fully device independent protocols. As a tool, we use the correspondence between Bell inequalities and dimension witnesses. We present a method for converting the former into the latter and vice versa. This relation provides us with interesting results for both scenarios. First, we find new random number generation protocols with higher bit rates for both the semi and fully device independent...

    Pełny tekst do pobrania w portalu

  • Total restrained bondage in graphs
    Publikacja

    - ACTA MATHEMATICA SINICA-ENGLISH SERIES - Rok 2013

    Podzbiór D zbioru wierzchołków grafu nazywamy zewnętrznie totalnym dominującym w grafie, jeśli każdy wierzchołek spoza D ma sąsiada zarówno w D jak i poza D. Moc najmniejszego zbioru o tej własności nazywamy liczbą dominowania zewnętrznie totalnego. W artykule badamy wpływ usuwania krawędzi na liczbę dominowania zewnętrznie totalnego, czyli liczbę zewnętrznego totalnego zniewolenie w grafach.

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2012
Rok 2011
Rok 2010
  • A note on the weakly convex and convex domination numbers of a torus

    W pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.

    Pełny tekst do pobrania w portalu

  • Co to jest czas?
    Publikacja

    - Rok 2010

    Święty Augustyn wypowiedział kiedyś takie słowa: "Czymże jest czas? Jeśli nikt mnie o to nie pyta, wiem. Jeśli pytającemu usiłuję wytłumaczyć, nie wiem." Nie ma wątpliwości, że czas jest czymś ważnym,a nawet bardzo ważnym - bez niego nic by się nie działo. Czy czas nie jest tym dobrem, którego nam brakuje najczęściej? Wielu filozofów widzi w czasie jedną z podstaw wszelkich sądów matematycznych.Strategiczną rolę czasu jeszcze bardziej...

Rok 2009
Rok 2008
  • Distance paired domination numbers of graphs
    Publikacja

    W pracy przedstawione są pewne własności liczb k-dominowania parami w grafach. Wykazane jest, że problem decyzyjny liczby k-dominowania parami jest problemem NP-zupełnym nawet dla grafów dwudzielnych. Przedstawione są ograniczenia górne i dolne dla liczby k-dominowania parami w drzewach i scharakteryzowane drzewa, w których te ograniczenia są osiągnięte.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Paired bondage in trees
    Publikacja

    W pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Some results on a trading model in a consensus list coloring
    Publikacja

    - Rok 2008

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Total restrained domination numbers of trees
    Publikacja

    Opisane są wszystkie drzewa, w których liczby dominowania totalnego i totalno - powściągniętego są sobie równe, a także podano dolne ograniczenie na liczbę dominowania totalno - powściągniętego w drzewach.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Weakly connected domination subdivision numbers

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

    Pełny tekst do pobrania w portalu

Rok 2007
Rok 2006
Rok 2005