A recognition algorithm for adjusted interval digraphs

DOI10.1016/J.DAM.2021.02.014zbMATH Open1506.05202arXiv1810.06162OpenAlexW3129783352MaRDI QIDQ2656971FDOQ2656971

Authors: Asahi Takaoka 

Publication date: 17 March 2021

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

Abstract: Min orderings give a vertex ordering characterization, common to some graphs and digraphs such as interval graphs, complements of threshold tolerance graphs (known as co-TT graphs), and two-directional orthogonal ray graphs. An adjusted interval digraph is a reflexive digraph that has a min ordering. Adjusted interval digraph can be recognized in $O(n^4)$ time, where $n$ is the number of vertices of the given graph. Finding a more efficient algorithm is posed as an open question. This note provides a new recognition algorithm with running time $O(n^3)$. The algorithm produces a min ordering if the given graph is an adjusted interval digraph.

Full work available at URL: https://arxiv.org/abs/1810.06162

Recommendations

• Adjusted interval digraphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Recognition and characterization of chronological interval digraphs
• Interval-like graphs and digraphs
• Recognizing interval digraphs and interval bigraphs in polynomial time

zbMATH Keywords

recognition algorithmadjusted interval digraphsmin ordering

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Interval digraphs: An analogue of interval graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On orthogonal ray graphs
• Threshold tolerance graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Min-Orderable Digraphs

Cited In (4)

• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• On the kernel and related problems in interval digraphs
• Recognition and characterization of chronological interval digraphs
• Title not available (Why is that?)

This page was built for publication: A recognition algorithm for adjusted interval digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656971)