BROWSE

Related Scientist

's photo.

수리및계산과학연구단
more info

ITEM VIEW & DOWNLOAD

Classes of intersection digraphs with good algorithmic properties

Cited 0 time in webofscience Cited 0 time in scopus
57 Viewed 0 Downloaded
Title
Classes of intersection digraphs with good algorithmic properties
Author(s)
Jaffke, Lars; O-joung Kwon; Telle, Jan Arne
Publication Date
2024-05
Journal
Journal of Graph Theory, v.106, no.1, pp.110 - 148
Publisher
John Wiley & Sons Inc.
Abstract
While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well-studied problems on digraphs, such as (Independent) Dominating Set, Kernel, and (Formula presented.) -Homomorphism. Third, we give a new width measure of digraphs, bi-mim-width, and show that the DLCV problems are polynomial-time solvable when we are provided a decomposition of small bi-mim-width. Fourth, we show that several classes of intersection digraphs have bounded bi-mim-width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi-mim-width, and therefore to obtain positive algorithmic results. © 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
URI
https://pr.ibs.re.kr/handle/8788114/14952
DOI
10.1002/jgt.23065
ISSN
0364-9024
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse