Minimum eccentricity shortest paths in some structured graph classes

DOI10.1007/978-3-662-53174-7_14MaRDI QIDQ2827811zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Arne Leitert

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.05109

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Abstract: We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary graphs (generalizing the previous result for trees) and give a generalised approach which allows to solve the problem in polynomial time for other graph classes. This includes chordal graphs, dually chordal graphs, graphs with bounded tree-length, and graphs with bounded hyperbolicity. Additionally, we give a simple algorithm to compute an additive approximation for graphs with bounded tree-length and graphs with bounded hyperbolicity.

Recommendations

• Minimum eccentricity shortest paths in some structured graph classes
• Minimum eccentricity shortest path problem with respect to structural parameters
• On the minimum eccentricity shortest path problem
• On the minimum eccentricity shortest path problem
• Finding a minimum path cover of a distance-hereditary graph in polynomial time

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Convexity in Graphs and Hypergraphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Line-distortion, bandwidth and path-length of a graph
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• On the minimum eccentricity shortest path problem
• Planar Formulae and Their Uses
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

Cited in

(9)

• Minimum eccentricity shortest path problem with respect to structural parameters
• On the minimum eccentricity shortest path problem
• Path eccentricity of graphs
• On the minimum eccentricity shortest path problem
• Parameterized algorithms for eccentricity shortest path problem
• On fixed-parameter solvability of the minimax path location problem
• Eccentricity function in distance-hereditary graphs
• Minimum eccentricity shortest paths in some structured graph classes
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem

This page was built for publication: Minimum eccentricity shortest paths in some structured graph classes

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