Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph

DOI10.1016/j.amc.2014.11.037zbMath1338.05263OpenAlexW1989997226MaRDI QIDQ299417

E. Kh. Gimadi

Publication date: 22 June 2016

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

Full work available at URL: https://doi.org/10.1016/j.amc.2014.11.037

zbMATH Keywords

performance guaranteesapproximation algorithmsasymptotic optimality\( m\)-layer planar assignment problemEuclidean \( m\)-PSPmetric \( m\)-weighted clique problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Safe and secure vehicle routing: a survey on minimization of risk exposure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Arrays of distinct representatives --- a very simple NP-complete problem
• The traveling salesman problem and its variations
• A strongly polynomial algorithm for the transportation problem
• Complexity of a 3-dimensional assignment problem
• Assignment Problems
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph