Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
From MaRDI portal
Publication:415269
DOI10.1016/j.dam.2011.04.016zbMath1236.05092MaRDI QIDQ415269
Jing Huang, Tomás Feder, Pavol Hell, Arash Rafiey
Publication date: 11 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.04.016
polynomial algorithms; interval graphs; dichotomy; adjusted interval digraphs; forbidden structure characterizations; interval digraphs; list homomorphism problems
Related Items
Bounded Tree-Width and CSP-Related Problems, Minimum Cost Homomorphisms to Reflexive Digraphs, Digraph matrix partitions and trigraph homomorphisms, The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops, Minimum Cost Homomorphism Dichotomy for Oriented Cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recognition and characterization of chronological interval digraphs
- Digraph matrix partitions and trigraph homomorphisms
- Some remarks on interval graphs
- A characterization of interval catch digraphs
- List homomorphisms to reflexive graphs
- Polynomial graph-colorings
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- List homomorphisms and circular arc graphs
- Incidence matrices and interval graphs
- Adjusted Interval Digraphs
- Complexity of conservative constraint satisfaction problems
- The LBFS Structure and Recognition of Interval Graphs
- Representation of a finite graph by a set of intervals on the real line
- Interval digraphs: An analogue of interval graphs
- Bi‐arc graphs and the complexity of list homomorphisms
