A recognition algorithm for adjusted interval digraphs

DOI10.1016/J.DAM.2021.02.014MaRDI QIDQ2656971zbMATH OpenOpenAlexFDO

Authors Asahi Takaoka

Publication date 17 March 2021

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

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

zbMATH Keywords

recognition algorithmadjusted interval digraphsmin ordering

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Recognition and characterization of chronological interval digraphs
• Adjusted interval digraphs
• scientific article; zbMATH DE number 1533814 (Why is no real title available?)
• On the kernel and related problems in interval digraphs

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)