Critical edges for the assignment problem: complexity and exact resolution

DOI10.1016/j.orl.2013.10.001zbMath1287.90080OpenAlexW2005659806MaRDI QIDQ2450758

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

complexityapproximationassignment problemexact algorithmmost vital edgesMIN edge blocker

Mathematics Subject Classification ID

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

Related Items (8)

An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ 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 ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Unnamed Item ⋮ Connectivity interdiction ⋮ Blocking total dominating sets via edge contractions

Cites Work

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

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