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

Survival Tree01:19

Survival Tree

128
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
 Building a Survival Tree
Constructing a...
128
Law of Independent Assortment02:03

Law of Independent Assortment

56.0K
While Mendel’s Law of Segregation states that the two alleles for one gene are separated into different gametes, a different question of how different genes are inherited remains. For example, is the gene for tall plants inherited with the gene for green peas? Mendel asked this question by experimenting with a dihybrid cross; a cross in which both parents are homozygous for two distinct traits resulting in an F1 generation that are heterozygous for both traits.
56.0K
Phylogenetic Trees03:21

Phylogenetic Trees

45.8K
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
45.8K
Maximum Power Flow and Line Loadability01:23

Maximum Power Flow and Line Loadability

148
The maximum power flow for lossy transmission lines is derived using ABCD parameters in phasor form. These parameters create a matrix relationship between the sending-end and receiving-end voltages and currents, allowing the determination of the receiving-end current. This relationship facilitates calculating the complex power delivered to the receiving end, from which real and reactive power components are derived.
148
Compacting Factor test01:22

Compacting Factor test

212
The compacting factor test is a method used to assess the workability of concrete. It is  especially suitable for concrete mixes containing aggregates up to one and a half inches in size. This test involves specialized equipment consisting of two truncated cone-shaped hoppers and a cylinder, all with polished interior surfaces to minimize friction.
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
212
Chromatin Packaging02:21

Chromatin Packaging

8.3K
8.3K

You might also read

Related Articles

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

Sort by
Same author

A linear time algorithm for linearizing quadratic and higher-order shortest path problems.

Mathematical programming·2025
Same author

Matroid bases with cardinality constraints on the intersection.

Mathematical programming·2022
Same author

Continuous facility location on graphs.

Mathematical programming·2022
Same author

The Steiner cycle and path cover problem on interval graphs.

Journal of combinatorial optimization·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

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: Aug 7, 2025

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.1K

Non-Preemptive Tree Packing.

Stefan Lendl1, Gerhard Woeginger2, Lasse Wulf3

  • 1Department of Operations and Information Systems, University of Graz, Graz, Styria Austria.

Algorithmica
|March 8, 2023
PubMed
Summary
This summary is machine-generated.

This study addresses the non-preemptive tree packing problem, focusing on maximizing graph connectivity over time. The problem is proven to be strongly NP-hard, limiting efficient approximation solutions.

Keywords:
Combinatorial optimizationKeeping a network connected over timeNon-preemptive schedulingSpanning tree packingTimevarying graphs

More Related Videos

A Simple Planting Technique for Re-establishing Trees Where Frequent Inundation Occurs
04:41

A Simple Planting Technique for Re-establishing Trees Where Frequent Inundation Occurs

Published on: January 26, 2018

6.3K
A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.4K

Related Experiment Videos

Last Updated: Aug 7, 2025

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.1K
A Simple Planting Technique for Re-establishing Trees Where Frequent Inundation Occurs
04:41

A Simple Planting Technique for Re-establishing Trees Where Frequent Inundation Occurs

Published on: January 26, 2018

6.3K
A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.4K

Area of Science:

  • Graph theory
  • Combinatorial optimization
  • Algorithm analysis

Background:

  • The non-preemptive tree packing problem involves activating edges with specific weights to maintain graph connectivity.
  • The objective is to maximize the total time the graph remains connected.

Purpose of the Study:

  • To analyze the computational complexity of the non-preemptive tree packing problem.
  • To investigate the feasibility of approximation algorithms and develop exact and parameterized algorithms.

Main Methods:

  • Complexity analysis to establish NP-hardness.
  • Investigation of approximation algorithms, including a greedy approach.
  • Development and analysis of parameterized and exact algorithms.

Main Results:

  • The problem is shown to be strongly NP-hard, even for graphs with treewidth 2.
  • A polynomial time approximation scheme (PTAS) is not possible unless P=NP.
  • Analysis of a greedy algorithm's performance and the development of new exact and parameterized algorithms.

Conclusions:

  • The non-preemptive tree packing problem is computationally challenging.
  • Efficient approximation is unlikely, necessitating the exploration of exact and parameterized algorithmic approaches.