Critical edges for the assignment problem: complexity and exact resolution

DOI10.1016/J.ORL.2013.10.001MaRDI QIDQ2450758zbMATH OpenOpenAlexFDO

Authors Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten

Publication date 15 May 2014

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2013.10.001

zbMATH Keywords

approximationassignment problemcomplexityexact algorithmMIN edge blockermost vital edges

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Parameterized Complexity of Edge Interdiction Problems
• Adjacency on the constrained assignment problem
• NP-completeness results for edge modification problems
• Tight approximation algorithms for maximum separable assignment problems
• Approximation algorithms for the partial assignment problem
• Approximability of Edge Matching Puzzles
• Approximation hardness of edge dominating set problems
• Approximation Algorithms for Edge-Covering Problem
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• On the complexity of some edge-partition problems for graphs

Cites work

• A note on shortest path, assignment, and transportation problems
• An algorithm for ranking assignments using reoptimization
• Approximation algorithms for NP-hard problems.
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Complexity of determining the most vital elements for the p-median and p-center location problems
• Deterministic network interdiction
• Efficient determination of the k most vital edges for the minimum spanning tree problem
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Matching interdiction
• On short paths interdiction problems: Total and node-wise limited interdiction
• On Syntactic versus Computational Views of Approximability
• The most vital nodes with respect to independent set and vertex cover

Cited in

(12)

• Connectivity interdiction
• Maximum shortest path interdiction problem by upgrading edges on trees under weighted l₁ norm
• Blocking total dominating sets via edge contractions
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Most vital vertices for the shortest s-t path problem: complexity and branch-and-cut algorithm
• Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance
• An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance
• scientific article; zbMATH DE number 1342136 (Why is no real title available?)
• Robust assignments via ear decompositions and randomized rounding
• Reducing the domination number of graphs via edge contractions
• Double interdiction problem on trees on the sum of root-leaf distances by upgrading edges
• Budget and profit approximations for spanning tree interdiction

This page was built for publication: Critical edges for the assignment problem: complexity and exact resolution

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