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

Linear Circuits01:17

Linear Circuits

842
A linear circuit is characterized by its output having a direct proportionality to its input, adhering to the linearity property, which encompasses the principles of homogeneity (scaling) and additivity. Homogeneity dictates that when the input, also referred to as the excitation, is multiplied by a constant factor, the output, known as the response, is correspondingly scaled by the same constant factor. For instance, if the current is multiplied by a constant 'k,' the voltage likewise...
842
Linear Momentum00:55

Linear Momentum

17.6K
The term momentum is used in various ways in everyday language, most of which are consistent with the precise scientific definition. Generally, momentum implies a tendency to continue on course—to move in the same direction; we tend to speak of sports teams or politicians gaining and maintaining the momentum to win.  Momentum is also associated with great mass and speed and is often considered when talking about collisions. For example, when rugby players collide and fall to the...
17.6K
Linearization and Approximation01:26

Linearization and Approximation

51
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
51
Application of Linearization and Approximation01:29

Application of Linearization and Approximation

87
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
87
Linear Momentum in Control Volume01:13

Linear Momentum in Control Volume

1.3K
Newton's second law is applied to obtain the linear momentum in a control volume in a fluid system. According to this law, the rate of change of linear momentum is equal to the sum of external forces acting on the system. When a control volume matches the fluid system at a specific moment, the forces acting on both are identical. Reynolds transport theorem helps explain this by breaking down the system's linear momentum into two components: the rate of change of linear momentum within...
1.3K
Application of the Linear Momentum Equation01:15

Application of the Linear Momentum Equation

425
The application of the linear momentum equation can be used to analyze the forces needed to hold a 180-degree pipe bend in place with flowing water. In this case, water flows through the bend with a constant cross-sectional area of 0.01 square meters and a flow velocity of 15 meters per second. The pressure at the entrance is 0.2 Megapascals and the pressure at the exit is 0.16 Megapascals.
The goal is to determine the force components in the x and y directions to hold the pipe in place. Since...
425

You might also read

Related Articles

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

Sort by
Same author

Achievement of Target Gain Larger than Unity in an Inertial Fusion Experiment.

Physical review letters·2024
Same author

Lawson Criterion for Ignition Exceeded in an Inertial Fusion Experiment.

Physical review letters·2022
Same author

Simultaneous visualization of wall motion, beam propagation, and implosion symmetry on the National Ignition Facility (invited).

The Review of scientific instruments·2018
Same author

Recreation-induced changes in boreal bird communities in protected areas.

Ecological applications : a publication of the Ecological Society of America·2010
Same author

Efficient, high-energy, narrow-band, blue-light source.

Optics letters·2009
Same author

A dissenting view on consent.

MCN. The American journal of maternal child nursing·1988
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: Jan 26, 2026

Counting and Determining the Viability of Cultured Cells
05:47

Counting and Determining the Viability of Cultured Cells

Published on: June 23, 2008

23.3K

Counting Linear Extensions: Parameterizations by Treewidth.

E Eiben1, R Ganian2, K Kangas3

  • 11Department of Informatics, University of Bergen, Bergen, Norway.

Algorithmica
|April 23, 2019
PubMed
Summary
This summary is machine-generated.

Counting linear extensions of posets is computationally hard. This study shows it is fixed-parameter intractable for cover graphs but tractable for incomparability graphs, using treewidth as a parameter.

Keywords:
Linear extensionsParameterized complexityPartially ordered setsStructural parametersTreewidth

More Related Videos

Linearization of the Bradford Protein Assay
06:35

Linearization of the Bradford Protein Assay

Published on: April 12, 2010

103.3K
Proboscis Extension Response PER Assay in Drosophila
23:42

Proboscis Extension Response PER Assay in Drosophila

Published on: April 29, 2007

31.2K

Related Experiment Videos

Last Updated: Jan 26, 2026

Counting and Determining the Viability of Cultured Cells
05:47

Counting and Determining the Viability of Cultured Cells

Published on: June 23, 2008

23.3K
Linearization of the Bradford Protein Assay
06:35

Linearization of the Bradford Protein Assay

Published on: April 12, 2010

103.3K
Proboscis Extension Response PER Assay in Drosophila
23:42

Proboscis Extension Response PER Assay in Drosophila

Published on: April 29, 2007

31.2K

Area of Science:

  • Discrete Mathematics
  • Theoretical Computer Science
  • Combinatorics

Background:

  • The problem of counting linear extensions of a poset is fundamental in order theory.
  • It has diverse applications across various scientific domains.
  • Understanding its computational complexity is crucial for practical applications.

Purpose of the Study:

  • To analyze the parameterized complexity of counting poset linear extensions.
  • To investigate this problem with respect to treewidth for two graph representations: cover and incomparability graphs.
  • To resolve an open problem concerning the fixed-parameter tractability of this counting problem.

Main Methods:

  • Parameterized complexity analysis.
  • Graph decomposition techniques, specifically treewidth.
  • Investigation of two graph representations: cover graphs and incomparability graphs of posets.

Main Results:

  • The problem is proven to be fixed-parameter intractable when parameterized by the treewidth of the cover graph.
  • This result resolves a recently posed open problem.
  • Conversely, the problem is shown to be fixed-parameter tractable when parameterized by the treewidth of the incomparability graph.

Conclusions:

  • The choice of graph representation significantly impacts the parameterized complexity of counting poset linear extensions.
  • Treewidth is a relevant parameter for analyzing this problem, exhibiting different tractability depending on the graph type.
  • The findings provide new insights into the computational landscape of poset enumeration problems.