Department of Algorithms and Systems Modelling - Administrative Units - Bridge of Knowledge

Search

Department of Algorithms and Systems Modelling

Filters

total: 103

  • Category
  • Year
  • Options

clear Chosen catalog filters disabled

Catalog Publications

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

    - Year 2022

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

    Full text to download in external service

Year 2021
  • An Efficient Noisy Binary Search in Graphs via Median Approximation
    Publication

    - LECTURE NOTES IN COMPUTER SCIENCE - Year 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...

    Full text to download in external service

Year 2019
Year 2018
  • On domination multisubdivision number of unicyclic graphs
    Publication

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

    Full text available to download

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

    Full text available to download

  • Total Domination Versus Domination in Cubic Graphs
    Publication

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

    Full text available to download

Year 2016
Year 2015
Year 2014
  • Some Progress on Total Bondage in Graphs
    Publication

    - GRAPHS AND COMBINATORICS - Year 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.

    Full text available to download

Year 2013
  • Relationship between semi- and fully-device-independent protocols
    Publication
    • 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 - Year 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...

    Full text available to download

  • Total restrained bondage in graphs
    Publication

    - ACTA MATHEMATICA SINICA-ENGLISH SERIES - Year 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.

    Full text to download in external service

Year 2012
Year 2011
Year 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.

    Full text available to download

  • Co to jest czas?
    Publication

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

Year 2009
Year 2008
  • Distance paired domination numbers of graphs
    Publication

    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.

    Full text to download in external service

  • Paired bondage in trees
    Publication

    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.

    Full text to download in external service

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

    - Year 2008

    Full text to download in external service

  • Total restrained domination numbers of trees
    Publication

    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.

    Full text to download in external service

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

    Full text available to download

Year 2007
Year 2006
Year 2005