Minimum cost and list homomorphisms to semicomplete digraphs

DOI10.1016/j.dam.2005.11.006zbMath1138.05032OpenAlexW2126491855MaRDI QIDQ2492190

Gregory Gutin, Arash Rafiey, Anders Yeo

Publication date: 9 June 2006

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

Full work available at URL: https://doi.org/10.1016/j.dam.2005.11.006

zbMATH Keywords

digraphhomomorphismsemicomplete digraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (15)

Minimum cost homomorphism dichotomy for oriented cycles ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ New plain-exponential time classes for graph homomorphism ⋮ Colouring, constraint satisfaction, and complexity ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ Multipartite tournaments: a survey ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ List H-coloring a graph by removing few vertices ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Introduction to the Maximum Solution Problem ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Augmenting graphs for independent sets
• On the complexity of H-coloring
• Polynomial graph-colorings
• A nice class for the vertex packing problem
• List homomorphisms and circular arc graphs
• Complexity of conservative constraint satisfaction problems
• On graphs with polynomially solvable maximum-weight clique problem
• The Complexity of Colouring by Semicomplete Digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Maximum weighted independent sets on transitive graphs and applications
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Algorithmic Applications in Management
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Minimum cost and list homomorphisms to semicomplete digraphs