Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
From MaRDI portal
Publication:415269
DOI10.1016/j.dam.2011.04.016zbMath1236.05092OpenAlexW2052776056MaRDI QIDQ415269
Pavol Hell, Tomás Feder, Arash Rafiey, Jing Huang
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 algorithmsinterval graphsdichotomyadjusted interval digraphsforbidden structure characterizationsinterval digraphslist homomorphism problems
Related Items
Unnamed Item ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ A recognition algorithm for adjusted interval digraphs ⋮ Chordal digraphs ⋮ Recognition and characterization of chronological interval digraphs ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ On the kernel and related problems in interval digraphs ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Unnamed Item ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Min-Orderable Digraphs ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Strict chordal and strict split digraphs ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Strong Chordality of Graphs with Possible Loops
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item