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

adjusted interval digraphsmin orderingrecognition algorithm

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.

Review text

Adjusted interval digraphs, being a generalization of interval graphs, are characterized by the existence of a min ordering and by the absence of invertible pairs. It can be shown that for a given graph with \(n\) nodes and \(m\) edges, the characterizations of adjusted interval digraphs yield a recognition algorithm with running time \(O(m^2+n^2)\), as opposed to a known \(O(n^4)\)-time recognition algorithm. The question of finding a linear-time recognition algorithm remains open. The purpose of this paper is to present an \(O(n^3)\)-time recognition algorithm for adjusted interval digraphs, thereby producing a min ordering or finding an invertible pair of the given graph if one exists. As a result, it also gives an alternative proof to show that a reflexive digraph has a min ordering if and only if it has no invertible pairs.

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)

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

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)