Některé parametrizované problémy spojené se Seidelovým přepnutím

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004897" target="_blank" >RIV/00216208:11320/07:00004897 - 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

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 usualquestion 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 and agraph without a forbidden subgraph.

Název v anglickém jazyce

Some Parameterized Problems Related to Seidel's Switching

Popis výsledku anglicky

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 usualquestion 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 and agraph without a forbidden subgraph.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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

WDS'07 Proceedings of Contributed Papers: Part I - Mathematics and Computer Sciences

ISBN

978-80-7378-023-4

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

23-28

Název nakladatele

Matfyzpress

Místo vydání

Prague

Místo konání akce

Prague

Datum konání akce

1. 1. 2007

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

CST - Celostátní akce

Kód UT WoS článku

—