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

14.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...
14.8K
Time-Series Graph00:54

Time-Series Graph

4.6K
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.6K
Velocity and Position by Graphical Method01:34

Velocity and Position by Graphical Method

8.4K
Velocity and position can be calculated from the known function of acceleration as a function of time. The total area under the acceleration-time graph and the velocity-time graph gives the change in velocity and position, respectively. In the case of an airplane, its acceleration is tracked using the inertial navigation system. The pilot provides the input of the airplane's initial position and velocity before takeoff. The inertial navigation system then uses the acceleration data to...
8.4K
Ogive Graph01:07

Ogive Graph

6.0K
An ogive graph is sometimes called a cumulative frequency polygon. It is one type of frequency polygon that shows cumulative frequency. In other words, the cumulative percentages are added to the graph from left to right. An ogive graph plots cumulative frequency on the vertical y-axis and class boundaries along the horizontal x-axis. It’s very similar to a histogram; only instead of rectangles, an ogive displays a single point where the top right of the rectangle would be. Creating this...
6.0K
Plotting of Topographic Maps01:29

Plotting of Topographic Maps

166
Topographic maps represent the Earth's surface features using contour lines, which connect points of equal elevation to create a two-dimensional representation of three-dimensional terrain. Creating a topographic map requires a systematic approach.Begin by plotting a scaled grid and marking intersections corresponding to the survey's elevation data points. Assign elevation values at these intersections to build the base map. Next, determine contour levels using a consistent contour interval,...
166
Bewley Lattice Diagram01:12

Bewley Lattice Diagram

907
The Bewley lattice diagram, developed by L. V. Bewley, effectively organizes the reflections occurring during transmission-line transients. It visually represents how voltage waves propagate and reflect within a transmission line, making it easier to understand the complex interactions that occur.
907

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

Non-Preemptive Tree Packing.

Algorithmica·2023
Same author

Matroid bases with cardinality constraints on the intersection.

Mathematical programming·2022
Same author

The Steiner cycle and path cover problem on interval graphs.

Journal of combinatorial optimization·2022
Same author

The multi-stripe travelling salesman problem.

Annals of operations research·2017
Same author

Complexity and approximability of double digest.

Journal of bioinformatics and computational biology·2005
Same journal

A better-than-1.6-approximation for prize-collecting TSP.

Mathematical programming·2026
Same journal

A <math><mrow><mfrac><mn>4</mn> <mn>3</mn></mfrac></mrow></math> -approximation for the maximum leaf spanning arborescence problem in DAGs.

Mathematical programming·2026
Same journal

An FPTAS for Connectivity Interdiction.

Mathematical programming·2026
Same journal

A first order method for linear programming parameterized by circuit imbalance.

Mathematical programming·2026
Same journal

Tight lower bounds for block-structured integer programs.

Mathematical programming·2026
Same journal

Accelerated first-order optimization under nonlinear constraints.

Mathematical programming·2026
See all related articles

Related Experiment Video

Updated: Sep 30, 2025

Using a Real-Time Locating System to Measure Walking Activity Associated with Wandering Behaviors Among Institutionalized Older Adults
04:13

Using a Real-Time Locating System to Measure Walking Activity Associated with Wandering Behaviors Among Institutionalized Older Adults

Published on: February 8, 2019

6.9K

Continuous facility location on graphs.

Tim A Hartmann1, Stefan Lendl2, Gerhard J Woeginger1

  • 1Department of Computer Science, RWTH Aachen, Aachen, Germany.

Mathematical Programming
|March 18, 2022
PubMed
Summary
This summary is machine-generated.

This study addresses the continuous facility location problem on graphs. It finds the problem is efficiently solvable for unit fractions of the covering range, but becomes NP-hard otherwise.

Keywords:
ComplexityCoveringGraph theoryLocation theoryParametrized complexity

More Related Videos

Trajectory Data Analyses for Pedestrian Space-time Activity Study
16:14

Trajectory Data Analyses for Pedestrian Space-time Activity Study

Published on: February 25, 2013

13.7K
Network Analysis of Foramen Ovale Electrode Recordings in Drug-resistant Temporal Lobe Epilepsy Patients
09:32

Network Analysis of Foramen Ovale Electrode Recordings in Drug-resistant Temporal Lobe Epilepsy Patients

Published on: December 18, 2016

12.6K

Related Experiment Videos

Last Updated: Sep 30, 2025

Using a Real-Time Locating System to Measure Walking Activity Associated with Wandering Behaviors Among Institutionalized Older Adults
04:13

Using a Real-Time Locating System to Measure Walking Activity Associated with Wandering Behaviors Among Institutionalized Older Adults

Published on: February 8, 2019

6.9K
Trajectory Data Analyses for Pedestrian Space-time Activity Study
16:14

Trajectory Data Analyses for Pedestrian Space-time Activity Study

Published on: February 25, 2013

13.7K
Network Analysis of Foramen Ovale Electrode Recordings in Drug-resistant Temporal Lobe Epilepsy Patients
09:32

Network Analysis of Foramen Ovale Electrode Recordings in Drug-resistant Temporal Lobe Epilepsy Patients

Published on: December 18, 2016

12.6K

Area of Science:

  • Graph Theory
  • Operations Research
  • Computational Geometry

Background:

  • The continuous facility location problem involves placing facilities to cover a given area.
  • This research focuses on covering undirected graphs with unit-length edges, allowing facilities on vertices and edges.

Purpose of the Study:

  • To determine the computational complexity of the continuous facility location problem based on the covering range parameter.
  • To analyze the parameterized complexity concerning the number of facilities required.

Main Methods:

  • Investigating the problem with a rational parameter representing the covering range.
  • Employing graph algorithms and complexity theory to analyze solvability and hardness.

Main Results:

  • The problem is polynomially solvable when the covering range is a unit fraction.
  • The problem is NP-hard for all non-unit fractions of the covering range.
  • The problem is fixed-parameter tractable for a small number of facilities but W[2]-hard for a larger number.

Conclusions:

  • The nature of the covering range (unit fraction vs. non-unit fraction) critically impacts the problem's computational complexity.
  • Understanding these complexities is crucial for efficient facility location in graph-based networks.