All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Target Set Selection in Dense Graph Classes

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386996" target="_blank" >RIV/00216208:11320/18:10386996 - isvavai.cz</a>

  • Alternative codes found

    RIV/68407700:21240/18:00326433

  • Result on the web

    <a href="http://drops.dagstuhl.de/opus/volltexte/2018/9966/pdf/LIPIcs-ISAAC-2018-18.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2018/9966/pdf/LIPIcs-ISAAC-2018-18.pdf</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.18" target="_blank" >10.4230/LIPIcs.ISAAC.2018.18</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Target Set Selection in Dense Graph Classes

  • Original language description

    In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

  • Continuities

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Others

  • Publication year

    2018

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    29th International Symposium on Algorithms and Computation (ISAAC 2018)

  • ISBN

    978-3-95977-094-1

  • ISSN

    1868-8969

  • e-ISSN

    neuvedeno

  • Number of pages

    13

  • Pages from-to

    1-13

  • Publisher name

    Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

  • Place of publication

    Dagstuhl, Germany

  • Event location

    Jiaoxi

  • Event date

    Dec 16, 2018

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article