Jove
Visualize
Contact Us

Related Concept Videos

The Tree of Life - Bacteria, Archaea, Eukaryotes02:40

The Tree of Life - Bacteria, Archaea, Eukaryotes

38.1K
The “tree of life” describes the evolution of life and the evolutionary relationships between organisms. The root of the tree is the common ancestor to all life on Earth. All other species radiate from this point, much like the branches of a tree. The numerous tips of these branches on the tree of life represent every living, or extant, species. Extinct species, which are species that no longer exist, can be found towards the center of the tree. Currently, these organisms, both...
38.1K
Mean free path and Mean free time01:22

Mean free path and Mean free time

5.1K
Consider the gas molecules in a cylinder. They move in a random motion as they collide with each other and change speed and direction. The average of all the path lengths between collisions is known as the "mean free path."
5.1K
Maximum Deflection01:13

Maximum Deflection

1.0K
When analyzing beams under unsymmetrical loads, such as a train moving on a bridge, it is crucial to accurately determine the points of maximum stress and deflection. The process involves identifying the maximum deflection of the beam, which may not always occur at its midpoint due to the uneven distribution of the load.
The maximum deflection occurs at a specific point, known as point O, where the tangent to the deflection curve is horizontal. To find point O, the slope of the tangent at any...
1.0K
Path Between Thermodynamics States01:21

Path Between Thermodynamics States

3.9K
Consider the two thermodynamic processes involving an ideal gas that are represented by paths AC and ABC in Figure 1:
3.9K
Interference: Path Lengths01:10

Interference: Path Lengths

1.9K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
1.9K
Maximum Power Transfer01:16

Maximum Power Transfer

869
Numerous practical applications within engineering disciplines, such as telecommunications, necessitate optimizing power delivery to a connected load. This pursuit, however, entails inherent internal losses, which can either equal or exceed the power supplied to the load. The Thevenin equivalent circuit is helpful in finding the maximum power a linear circuit can deliver to a load. It is assumed in this context that the load resistance can be adjusted.
By substituting the entire circuit with...
869

You might also read

Related Articles

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

Sort by
Same author

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy.

Algorithmica·2020
Same author

Improved bounds for minimal feedback vertex sets in tournaments.

Journal of graph theory·2018
See all related articles
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 Experiment Video

Updated: Jan 26, 2026

Area-based Image Analysis Algorithm for Quantification of Macrophage-fibroblast Cocultures
07:05

Area-based Image Analysis Algorithm for Quantification of Macrophage-fibroblast Cocultures

Published on: February 15, 2022

2.9K

New algorithms for maximum disjoint paths based on tree-likeness.

Krzysztof Fleszar1, Matthias Mnich2,3, Joachim Spoerhase4

  • 11Department 1: Algorithms and Complexity, Max-Planck-Institut für Informatik, Campus E1 4, 66123 Saarbrücken, Germany.

Mathematical Programming
|April 9, 2019
PubMed
Summary
This summary is machine-generated.

This study improves approximation algorithms for routing problems, offering better solutions for maximum edge-disjoint paths and optimal solutions for maximum node-disjoint paths, even in complex graphs.

Keywords:
Approximation algorithmDisjoint pathsFeedback vertex setFixed-parameter algorithm

More Related Videos

Transcript and Metabolite Profiling for the Evaluation of Tobacco Tree and Poplar as Feedstock for the Bio-based Industry
10:50

Transcript and Metabolite Profiling for the Evaluation of Tobacco Tree and Poplar as Feedstock for the Bio-based Industry

Published on: May 16, 2014

15.7K
A Venturi Effect Can Help Cure Our Trees
05:26

A Venturi Effect Can Help Cure Our Trees

Published on: October 1, 2013

18.4K

Related Experiment Videos

Last Updated: Jan 26, 2026

Area-based Image Analysis Algorithm for Quantification of Macrophage-fibroblast Cocultures
07:05

Area-based Image Analysis Algorithm for Quantification of Macrophage-fibroblast Cocultures

Published on: February 15, 2022

2.9K
Transcript and Metabolite Profiling for the Evaluation of Tobacco Tree and Poplar as Feedstock for the Bio-based Industry
10:50

Transcript and Metabolite Profiling for the Evaluation of Tobacco Tree and Poplar as Feedstock for the Bio-based Industry

Published on: May 16, 2014

15.7K
A Venturi Effect Can Help Cure Our Trees
05:26

A Venturi Effect Can Help Cure Our Trees

Published on: October 1, 2013

18.4K

Area of Science:

  • Theoretical Computer Science
  • Graph Algorithms
  • Approximation Algorithms

Background:

  • The approximability of maximum edge-disjoint paths (MaxEDP) and maximum node-disjoint paths (MaxNDP) is a significant open problem in approximation algorithms.
  • Existing approximation algorithms for MaxEDP/MaxNDP have limitations, with a notable gap between known lower and upper bounds.
  • The feedback vertex set number (r) quantifies a graph's deviation from being a forest, impacting routing complexities.

Purpose of the Study:

  • To develop improved approximation algorithms for MaxEDP and MaxNDP problems.
  • To establish new theoretical bounds for these routing problems, particularly in relation to the feedback vertex set number.
  • To investigate the parameterized complexity of MaxEDP and MaxNDP.

Main Methods:

  • Development of a new approximation algorithm for MaxEDP with improved performance guarantees.
  • Design of an exact algorithm for MaxNDP with significantly reduced runtime complexity.
  • Analysis of problem hardness using parameterized complexity, specifically concerning the feedback vertex set number.

Main Results:

  • An O(r log n)-approximation algorithm for MaxEDP, strengthening existing results.
  • An exact algorithm for MaxNDP running in O(r^k * poly(n)) time, a substantial improvement.
  • Demonstration that MaxEDP and MaxNDP are W[1]-hard parameterized by r, implying limited tractability.

Conclusions:

  • The study provides significant advancements in the approximability and efficiency of solving MaxEDP and MaxNDP.
  • The findings highlight the relevance of the feedback vertex set number as a parameter for these routing problems.
  • The established hardness results suggest that the developed approximation algorithms are near-optimal for small values of r.