Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Woodward–Hoffmann Selection Rules and Microscopic Reversibility01:34

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

4.3K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
4.3K
Constraints and Statical Determinacy01:26

Constraints and Statical Determinacy

1.1K
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
1.1K
Stability of Equilibrium Configuration: Problem Solving01:13

Stability of Equilibrium Configuration: Problem Solving

1.2K
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
1.2K
Alternative Sets of Equilibrium Equations01:31

Alternative Sets of Equilibrium Equations

1.2K
When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
1.2K
Incomplete Dominance01:43

Incomplete Dominance

32.9K
Gregor Mendel's work (1822 - 1884) was primarily focused on pea plants. Through his initial experiments, he determined that every gene in a diploid cell has two variants called alleles inherited from each parent. He suggested that amongst these two alleles, one allele is dominant in character and the other recessive. The combination of alleles determines the phenotype of a gene in an organism.
32.9K
Statically Indeterminate Problem Solving01:16

Statically Indeterminate Problem Solving

895
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
895

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Scheduling cool jobs when processing heats them.

Journal of scheduling·2026
Same author

Note on extremal problems about connected subgraph sums.

Graphs and combinatorics·2026
Same author

On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan.

Algorithmica·2022
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
Same journal

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in [Formula: see text].

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Apr 21, 2026

New Variations for Strategy Set-shifting in the Rat
09:45

New Variations for Strategy Set-shifting in the Rat

Published on: January 23, 2017

8.7K

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Hans L Bodlaender1, Carla Groenland2, Céline M F Swennenhuis3

  • 1Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands.

Algorithmica
|April 20, 2026
PubMed
Summary
This summary is machine-generated.

This study resolves the parameterized complexity of independent set and dominating set reconfiguration problems. Token sliding and token jumping are shown to be equivalent, simplifying reconfiguration analysis.

Keywords:
Dominating set reconfigurationIndependent set reconfigurationParameterized complexityW-hierarchyXLXNLXNLP

More Related Videos

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.7K
RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.5K

Related Experiment Videos

Last Updated: Apr 21, 2026

New Variations for Strategy Set-shifting in the Rat
09:45

New Variations for Strategy Set-shifting in the Rat

Published on: January 23, 2017

8.7K
Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.7K
RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.5K

Area of Science:

  • Computational Complexity Theory
  • Graph Theory
  • Discrete Mathematics

Background:

  • Independent Set Reconfiguration and Dominating Set Reconfiguration are key problems in computational complexity.
  • Previous research established W[1]-hardness and W[2]-hardness for certain variants, leaving a gap in understanding their full parameterized complexity.

Purpose of the Study:

  • To determine the precise parameterized complexity of various independent set and dominating set reconfiguration problems.
  • To establish the relationship between token sliding and token jumping reconfiguration variants.
  • To introduce and analyze partitioned variants of token sliding and token jumping.

Main Methods:

  • Parameterized complexity analysis using complexity classes XL, XNL, and XNLP.
  • Establishing pl-reductions between different reconfiguration variants.
  • Analyzing the impact of input encoding (binary vs. unary) for the maximum sequence length parameter.

Main Results:

  • Both independent set reconfiguration and dominating set reconfiguration are shown to be XL-complete (no move limit), XNL-complete (binary input for length limit ℓ), and XNLP-complete (unary input for length limit ℓ).
  • Membership in W[1] and W[2] classes is proven for the respective parameterized problems.
  • Token sliding and token jumping are demonstrated to be equivalent under pl-reductions across all considered variants.
  • Partitioned variants of token jumping and sliding were introduced, with pl-reductions established between them.

Conclusions:

  • The parameterized complexity landscape for independent set and dominating set reconfiguration is now fully settled.
  • The equivalence of token sliding and token jumping simplifies the study of reconfiguration problems.
  • The introduction of partitioned variants offers new avenues for precise control over reconfiguration sequences and token counts.