On fixed-parameter solvability of the minimax path location problem

DOI10.1007/S42967-022-00238-6MaRDI QIDQ6063573zbMATH OpenFDO

Authors Hao Lin, Cheng He

Publication date 12 December 2023

Published in Communications on Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S42967-022-00238-6

zbMATH Keywords

discrete locationfixed-parameter solvabilitygraph characterizationpath locationpolynomial-time algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Minimum eccentricity shortest path problem with respect to structural parameters
• On locating a single path-like facility in a general graph
• Minimum eccentricity shortest paths in some structured graph classes
• Path eccentricity of graphs
• Inverse eccentric vertex problem on networks

Cites work

• A linear algorithm for a core of a tree
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Combinatorial optimization. Theory and algorithms.
• Conditional location of path and tree shaped facilities on trees
• Geometric complexity of some location problems
• Graph theory
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved algorithms for some competitive location centroid problems on paths, trees and graphs
• On locating path- or tree-shaped facilities on networks
• On the complexity of locating linear facilities in the plane
• Optimal algorithms for the path/tree-shaped facility location problems in trees
• Optimal location of a path or tree on a network with cycles
• Reliability problems in multiple path-shaped facility location on networks
• The location of median paths on grid graphs
• The optimal location of a path or tree in a tree network
• Two paths location of a tree with positive or negative weights

Cited in

(2)

• On a negative-equivalency theorem in associative optimal path problems
• Global optimization: On pathlengths in min-max graphs

This page was built for publication: On fixed-parameter solvability of the minimax path location problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063573)