Wyniki wyszukiwania dla: PATHWIDTH - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: PATHWIDTH

Wyniki wyszukiwania dla: PATHWIDTH

  • From Pathwidth to Connected Pathwidth

    W pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Zero-visibility cops and robber and the pathwidth of a graph

    Publikacja

    - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2015

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Finding small-width connected path decompositions in polynomial time

    Publikacja

    A connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Zero-Visibility Cops and Robber Game on a Graph

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2013

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The complexity of minimum-length path decompositions

    Publikacja

    We consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scanning networks with cactus topology

    Publikacja
    • Ł. Wrona

    - Rok 2008

    The family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...

  • On Tradeoffs Between Width- and Fill-like Graph Parameters

    In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Multi-agent graph searching and exploration algorithms

    Publikacja

    - Rok 2020

    A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...

    Pełny tekst do pobrania w portalu

  • Distributed graph searching with a sense of direction

    In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...

    Pełny tekst do pobrania w serwisie zewnętrznym