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

Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

12.5K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.5K
Introduction to Test of Independence01:21

Introduction to Test of Independence

2.3K
In statistics, the term independence means that one can directly obtain the probability of any event involving both variables by multiplying their individual probabilities. Tests of independence are chi-square tests involving the use of a contingency table of observed (data) values.
The test statistic for a test of independence is similar to that of a goodness-of-fit test:
2.3K
Parametric Survival Analysis: Weibull and Exponential Methods01:14

Parametric Survival Analysis: Weibull and Exponential Methods

488
Parametric survival analysis models survival data by assuming a specific probability distribution for the time until an event occurs. The Weibull and exponential distributions are two of the most commonly used methods in this context, due to their versatility and relatively straightforward application.
Weibull Distribution
The Weibull distribution is a flexible model used in parametric survival analysis. It can handle both increasing and decreasing hazard rates, depending on its shape parameter...
488
Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

9.7K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
9.7K
Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

769
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
769
Time-Series Graph00:54

Time-Series Graph

4.4K
A time-series graph is a line graph with repeated measurements taken at successive intervals of time. It is also called a time series chart. To construct a time-series graph, one must look at both pieces of a paired data set. The horizontal axis is used to plot the time increments, and the vertical axis is used to plot the values of the variable that one is measuring. By using the axes in this way, each point on the graph will correspond to time and a measured quantity. The points on the graph...
4.4K

You might also read

Related Articles

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

Sort by
Same author

(Re)packing Equal Disks into Rectangle.

Discrete & computational geometry·2024
Same author

Diverse collections in matroids and graphs.

Mathematical programming·2024
Same author

New algorithms for structure informed genome rearrangement.

Algorithms for molecular biology : AMB·2023
Same author

Special Issue Dedicated to the 16th International Symposium on Parameterized and Exact Computation.

Algorithmica·2022
Same author

Parameterized Complexity of Directed Spanner Problems.

Algorithmica·2022
Same author

Approximate search for known gene clusters in new genomes using PQ-trees.

Algorithms for molecular biology : AMB·2021
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

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

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
See all related articles

Related Experiment Video

Updated: Jul 25, 2025

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
05:12

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data

Published on: January 16, 2019

11.5K

Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number.

Pranabendu Misra1, Saket Saurabh2, Roohani Sharma3

  • 1Chennai Mathematical Institute, Chennai, India.

Algorithmica
|June 26, 2023
PubMed
Summary
This summary is machine-generated.

This study shows that algorithms with sub-exponential time complexity can solve complex cut problems on digraphs with bounded independence number, generalizing previous tournament results. This expands algorithmic possibilities for these graph classes.

Keywords:
Bounded independence number digraphDirected cutwidthDirected feedback arc setOptimal linear arrangementSub-exponential fixed-parameter tractable algorithms

More Related Videos

Evidence-based Knowledge Synthesis and Hypothesis Validation: Navigating Biomedical Knowledge Bases via Explainable AI and Agentic Systems
05:47

Evidence-based Knowledge Synthesis and Hypothesis Validation: Navigating Biomedical Knowledge Bases via Explainable AI and Agentic Systems

Published on: June 13, 2025

332
Author Spotlight: Advancing Large-Scale Neural Dynamics Through HD-MEA Technology
09:44

Author Spotlight: Advancing Large-Scale Neural Dynamics Through HD-MEA Technology

Published on: March 8, 2024

4.9K

Related Experiment Videos

Last Updated: Jul 25, 2025

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
05:12

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data

Published on: January 16, 2019

11.5K
Evidence-based Knowledge Synthesis and Hypothesis Validation: Navigating Biomedical Knowledge Bases via Explainable AI and Agentic Systems
05:47

Evidence-based Knowledge Synthesis and Hypothesis Validation: Navigating Biomedical Knowledge Bases via Explainable AI and Agentic Systems

Published on: June 13, 2025

332
Author Spotlight: Advancing Large-Scale Neural Dynamics Through HD-MEA Technology
09:44

Author Spotlight: Advancing Large-Scale Neural Dynamics Through HD-MEA Technology

Published on: March 8, 2024

4.9K

Area of Science:

  • Graph theory
  • Theoretical computer science
  • Algorithm design

Background:

  • Digraphs of bounded independence number generalize tournaments.
  • These digraphs are structured for algorithmic exploitation.
  • Parameterized algorithms for cut problems on tournaments are known.

Purpose of the Study:

  • To demonstrate that cut problems solvable with sub-exponential parameterized algorithms on tournaments are also solvable on digraphs of bounded independence number.
  • To extend the applicability of advanced algorithmic techniques to a broader class of graphs.
  • To strengthen the algorithmic potential of digraphs with bounded independence number.

Main Methods:

  • Leveraging the generic approach by Fomin and Pilipczuk for parameterized algorithms.
  • Bounding the number of k-cuts in digraphs of bounded independence number by a sub-exponential function.
  • Employing chromatic coding, inductive reasoning, and structural graph properties.

Main Results:

  • Several cut problems, including Directed Feedback Arc Set, Directed Cutwidth, and Optimal Linear Arrangement, admit sub-exponential time parameterized algorithms on digraphs of bounded independence number.
  • A key combinatorial result establishes a sub-exponential bound on the number of k-cuts for yes-instances of these problems.
  • The findings generalize and extend previous algorithmic results from tournaments to digraphs of bounded independence number.

Conclusions:

  • Digraphs of bounded independence number possess sufficient structure for advanced algorithmic techniques, particularly for cut problems.
  • The study provides a theoretical foundation for developing efficient parameterized algorithms on these graph classes.
  • This research significantly broadens the scope of problems amenable to sub-exponential time parameterized solutions in graph theory.