Characterizations and Directed Path-Width of Sequence Digraphs

CC BY

Lưu vào:
Hiển thị chi tiết
Tác giả chính: Frank, Gurski, Carolin, Rehs, Jochen, Rethmann
Định dạng: Sách
Ngôn ngữ:English
Nhà xuất bản: Springer 2023
Chủ đề:
Truy cập trực tuyến:https://link.springer.com/article/10.1007/s00224-022-10104-w
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7379
Từ khóa: Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
id oai:localhost:PNK-7379
record_format dspace
spelling oai:localhost:PNK-73792023-03-31T06:47:48Z Characterizations and Directed Path-Width of Sequence Digraphs Frank, Gurski Carolin, Rehs Jochen, Rethmann input digraph G = (V,A) NP-hard problem CC BY Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph G = (V,A) by a number k of sequences with entries from V, such that (u,v) ∈ A if and only if in one of the sequences there is an occurrence of u appearing before an occurrence of v. We present several graph theoretical properties of these digraphs. Among these we give forbidden subdigraphs of digraphs which can be defined by k = 1 sequence, which is a subclass of semicomplete digraphs. 2023-03-31T06:47:44Z 2023-03-31T06:47:44Z 2023 Book https://link.springer.com/article/10.1007/s00224-022-10104-w https://dlib.phenikaa-uni.edu.vn/handle/PNK/7379 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic input digraph G = (V,A)
NP-hard problem
spellingShingle input digraph G = (V,A)
NP-hard problem
Frank, Gurski
Carolin, Rehs
Jochen, Rethmann
Characterizations and Directed Path-Width of Sequence Digraphs
description CC BY
format Book
author Frank, Gurski
Carolin, Rehs
Jochen, Rethmann
author_facet Frank, Gurski
Carolin, Rehs
Jochen, Rethmann
author_sort Frank, Gurski
title Characterizations and Directed Path-Width of Sequence Digraphs
title_short Characterizations and Directed Path-Width of Sequence Digraphs
title_full Characterizations and Directed Path-Width of Sequence Digraphs
title_fullStr Characterizations and Directed Path-Width of Sequence Digraphs
title_full_unstemmed Characterizations and Directed Path-Width of Sequence Digraphs
title_sort characterizations and directed path-width of sequence digraphs
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s00224-022-10104-w
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7379
_version_ 1761912525881868288
score 8.891145