Level of repair analysis and minimum cost homomorphisms of graphs

DOI10.1016/j.dam.2005.06.012zbMath1131.90020OpenAlexW2046527740MaRDI QIDQ2492189

Arash Rafiey, Anders Yeo, Michael Tso, Gregory Gutin

Publication date: 9 June 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://eprints.maths.manchester.ac.uk/570/1/Level_of_Repair.pdf

zbMATH Keywords

independent sets in graphshomomorphisms of graphslevel of repair analysiscomputational logistics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Reliability, availability, maintenance, inspection in operations research (90B25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Related Items (20)

Minimum cost homomorphism dichotomy for oriented cycles ⋮ Critical and maximum independent sets of a graph ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Critical properties of bipartite permutation graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ New plain-exponential time classes for graph homomorphism ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ The complexity of soft constraint satisfaction ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ The expressive power of binary submodular functions ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ An efficient model formulation for level of repair analysis ⋮ Unnamed Item ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Unnamed Item ⋮ Introduction to the Maximum Solution Problem ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Cites Work

• On the complexity of H-coloring
• A combinatorial approach to level of repair analysis
• List homomorphisms and circular arc graphs
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• On Finding Critical Independent and Vertex Sets
• Improved Algorithms for Bipartite Network Flow
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Level of repair analysis and minimum cost homomorphisms of graphs