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

Vertical Curve: Problem Solving01:23

Vertical Curve: Problem Solving

149
Vertical curves provide the transition between two roadway grades, ensuring safety, comfort, and functionality. Calculating elevations at specific stations along the curve involves several systematic steps based on the curve's geometry and provided design parameters.The vertical curve is defined by its length, grades, Point of Vertical Intersection (P.V.I.) location, and P.V.I. elevation. The stations of the Point of Vertical Curvature (P.V.C.), where the curve begins, and the Point of Vertical...
149
Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

783
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...
783
Transformation of Plane Strain01:12

Transformation of Plane Strain

227
When analyzing elongated structures like bars subjected to uniformly distributed loads, it is essential to understand the transformation of plane strain when coordinate axes are rotated. This transformation helps to assess how material deformation characteristics vary with orientation, which is crucial in materials science and structural engineering.
Under plane strain conditions, typical for members where one dimension significantly exceeds the others, deformations and resultant strains are...
227
Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

12.8K
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.8K
Collisions in Multiple Dimensions: Problem Solving01:06

Collisions in Multiple Dimensions: Problem Solving

4.3K
In multiple dimensions, the conservation of momentum applies in each direction independently. Hence, to solve collisions in multiple dimensions, we should write down the momentum conservation in each direction separately. To help understand collisions in multiple dimensions, consider an example.
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
4.3K
Plastic Deformations of Members with a Single Plane of Symmetry01:21

Plastic Deformations of Members with a Single Plane of Symmetry

118
When a structural member undergoes plastic deformation due to bending, it is crucial to understand the position of the neutral axis and the stress distribution. This member, characterized by a single plane of symmetry, exhibits a uniform stress distribution, with negative stress above the neutral axis and positive stress below. Notably, the neutral axis does not align with the centroid of the cross-section. This misalignment is typical in cases where the cross-section is not rectangular or...
118

You might also read

Related Articles

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

Sort by
Same author

In and beyond the Griffiths phase: A large-deviation study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model.

Physical review. E·2024
Same author

Statistical methods for linking material composition to recombination losses in optoelectronic devices.

The Review of scientific instruments·2024
Same author

Metastate analysis of the ground states of two-dimensional Ising spin glasses.

Physical review. E·2023
Same author

Ordering behavior of the two-dimensional Ising spin glass with long-range correlated disorder.

Physical review. E·2021
Same author

Directed negative-weight percolation.

Physical review. E·2019
Same author

Distribution of diameters for Erdős-Rényi random graphs.

Physical review. E·2018

Related Experiment Video

Updated: Aug 24, 2025

Designing CAD/CAM Surgical Guides for Maxillary Reconstruction Using an In-house Approach
08:01

Designing CAD/CAM Surgical Guides for Maxillary Reconstruction Using an In-house Approach

Published on: August 24, 2018

9.1K

Cutting-plane algorithms and solution whitening for the vertex-cover problem.

G Claussen1, A K Hartmann1

  • 1Institut für Physik, Universität Oldenburg, Carl-von-Ossietzky-Straße 9-11, 26111 Oldenburg, Germany.

Physical Review. E
|October 21, 2022
PubMed
Summary

This study numerically investigates the vertex-cover problem using linear programming and cutting-plane methods on random graphs. Cutting-plane methods improve solution completeness, revealing a new algorithmic transition point.

More Related Videos

Digital Hybrid Model Preparation for Virtual Planning of Reconstructive Dentoalveolar Surgical Procedures
09:10

Digital Hybrid Model Preparation for Virtual Planning of Reconstructive Dentoalveolar Surgical Procedures

Published on: August 5, 2021

1.8K
Hybrid-Cut: An Improved Sectioning Method for Recalcitrant Plant Tissue Samples
09:38

Hybrid-Cut: An Improved Sectioning Method for Recalcitrant Plant Tissue Samples

Published on: November 23, 2016

19.1K

Related Experiment Videos

Last Updated: Aug 24, 2025

Designing CAD/CAM Surgical Guides for Maxillary Reconstruction Using an In-house Approach
08:01

Designing CAD/CAM Surgical Guides for Maxillary Reconstruction Using an In-house Approach

Published on: August 24, 2018

9.1K
Digital Hybrid Model Preparation for Virtual Planning of Reconstructive Dentoalveolar Surgical Procedures
09:10

Digital Hybrid Model Preparation for Virtual Planning of Reconstructive Dentoalveolar Surgical Procedures

Published on: August 5, 2021

1.8K
Hybrid-Cut: An Improved Sectioning Method for Recalcitrant Plant Tissue Samples
09:38

Hybrid-Cut: An Improved Sectioning Method for Recalcitrant Plant Tissue Samples

Published on: November 23, 2016

19.1K

Area of Science:

  • Computational Complexity
  • Combinatorial Optimization
  • Graph Theory

Background:

  • The vertex-cover (VC) problem is NP-hard, posing significant computational challenges.
  • Standard linear programming (LP) algorithms like Simplex (SX) can fail to find complete solutions for complex graphs.
  • Cutting-plane (CP) methods offer potential improvements for solving LPs with incomplete solutions.

Purpose of the Study:

  • To numerically investigate the phase-transition behavior of the vertex-cover problem.
  • To evaluate the effectiveness of cutting-plane methods (Gomory and {0,1/2} cuts) in obtaining complete solutions.
  • To identify and characterize algorithmic transitions in solving the VC problem.

Main Methods:

  • Numerical analysis of the vertex-cover problem on random graph ensembles.
  • Application of linear programming (LP) with the Simplex (SX) algorithm.
  • Implementation and evaluation of cutting-plane (CP) methods, specifically Gomory and {0,1/2} cuts.
  • Measurement of solution completeness probability as a function of average node degree (c).

Main Results:

  • Cutting-plane methods enhance the boundary of complete solutions compared to the pure Simplex algorithm.
  • An algorithmic transition is observed around c≈2.90(2), distinct from the replica-symmetry breaking (RSB) transition at c≈2.718.
  • The study quantifies the transition between easy and hard solvability in terms of numerical effort.
  • Vertex whitening, a measure of solution degeneracy, is slightly affected by the RSB transition.

Conclusions:

  • Cutting-plane methods are effective in improving the solvability of the vertex-cover problem on random graphs.
  • The findings suggest the existence of a novel algorithmic transition in solving this NP-hard problem.
  • Further research into vertex whitening may provide deeper insights into solution properties and algorithmic behavior.