Some Parameterized Problems Related to Seidel's Switching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00206097" target="_blank" >RIV/00216208:11320/08:00206097 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Some Parameterized Problems Related to Seidel's Switching

Popis výsledku v původním jazyce

Annotation in the original language is: Seidel's switching of vertex set is an operation, which deletes edges leaving this set from the graph and adds those edges between the set and the rest of the graph, that weren't there originally. Other edges remain untouched by this operation. The usual question in parameterized complexity is whether the exponential part of the algorithms for hard problems can be bounded by some function of only selected parameter, which we assume to be small. We study the complexity of a question, if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized view. We show fixed parameter tractability of switching to a regular graph, to a graph with bounded degree of vertices, or with bounded number of edges, a graph without a forbidden subgraph and a bipartite graph.

Název v anglickém jazyce

Some Parameterized Problems Related to Seidel's Switching

Popis výsledku anglicky

Annotation in the original language is: Seidel's switching of vertex set is an operation, which deletes edges leaving this set from the graph and adds those edges between the set and the rest of the graph, that weren't there originally. Other edges remain untouched by this operation. The usual question in parameterized complexity is whether the exponential part of the algorithms for hard problems can be bounded by some function of only selected parameter, which we assume to be small. We study the complexity of a question, if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized view. We show fixed parameter tractability of switching to a regular graph, to a graph with bounded degree of vertices, or with bounded number of edges, a graph without a forbidden subgraph and a bipartite graph.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the International Workshop on Combinatorial Algorithms 2007

ISBN

978-1-904987-67-3

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

—

Název nakladatele

College Publications

Místo vydání

United Kingdom

Místo konání akce

United Kingdom

Datum konání akce

1. 1. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—