Universität zu Köln

Apke, Alexander and Schrader, Rainer ORCID: 0000-0001-6635-0132 (2021). A characterization of interval orders with semiorder dimension two. Discret Appl. Math., 297. S. 142 - 151. AMSTERDAM: ELSEVIER. ISSN 1872-6771

Full text not available from this repository.

Abstract

Given a partial order Q, its semiorder dimension is the smallest number of semiorders whose intersection is Q. When we look at the class of partial orders of fixed semiorder dimension k, no characterization is known, even in the case k = 2. In this paper, we give a characterization of the class of interval orders with semiorder dimension two. It follows from our results that partial orders that are interval orders with semiorder dimension two can be recognized efficiently. As our characterization makes use of a certain substructure, we also discuss the possibility of a forbidden suborder characterization. We give a partial answer to this question by listing all forbidden suborders for a special case. We further transfer our characterization result to the class of interval graphs that induce orders with semiorder dimension two. (C) 2021 Published by Elsevier B.V.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Apke, Alexander UNSPECIFIED UNSPECIFIED UNSPECIFIED Schrader, Rainer UNSPECIFIED orcid.org/0000-0001-6635-0132 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-566274
DOI:	10.1016/j.dam.2021.02.010
Journal or Publication Title:	Discret Appl. Math.
Volume:	297
Page Range:	S. 142 - 151
Date:	2021
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-6771
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TRAPEZOID GRAPHS; PROPER; RECOGNITION; TOLERANCE Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/56627