Characterizations and Directed Path-Width of Sequence Digraphs
CC BY
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Đị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.8894005 |