About: Parameterized Problems Related to Seidel''s Switching

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Parameterized Problems Related to Seidel''s Switching Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1531
Description	Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. (en)
Title	Parameterized Problems Related to Seidel''s Switching Parameterized Problems Related to Seidel''s Switching (en)
skos:prefLabel	Parameterized Problems Related to Seidel''s Switching Parameterized Problems Related to Seidel''s Switching (en)
skos:notation	RIV/00216208:11320/11:10100314!RIV12-MSM-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021620838), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Kratochvíl, Jan Jelínková, Eva Suchý, Ondřej
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	219534
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/11:10100314
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Parameterized Complexity; Computational Complexity; Seidel's Switching (en)
http://linked.open.../riv/klicoveSlovo	Computational Complexity Seidel's Switching Parameterized Complexity
http://linked.open...odStatuVydavatele	FR - Francouzská republika
http://linked.open...ontrolniKodProRIV	[0EF339C46EA0]
http://linked.open...i/riv/nazevZdroje	Discrete Mathematics and Theoretical Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	13
http://linked.open...iv/tvurceVysledku	Hliněný, Petr Jelínková, Eva Kratochvíl, Jan Suchý, Ondřej
http://linked.open...ain/vavai/riv/wos	000290721600002
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky Highly Parallel and Distributed Computing Systems
issn	1365-8050
number of pages	24 (xsd:int)
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Parameterized Problems Related to Seidel''s Switching Parameterized Problems Related to Seidel''s Switching

Faceted Search & Find service v1.16.116 as of Feb 22 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3239 as of Feb 22 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software