Thông tin tài liệu
Thông tin siêu dữ liệu biểu ghi
| Trường DC | Giá trị | Ngôn ngữ |
|---|---|---|
| dc.contributor.author | Frank, Gurski | - |
| dc.contributor.author | Carolin, Rehs | - |
| dc.contributor.author | Jochen, Rethmann | - |
| dc.date.accessioned | 2023-03-31T06:47:44Z | - |
| dc.date.available | 2023-03-31T06:47:44Z | - |
| dc.date.issued | 2023 | - |
| dc.identifier.uri | https://link.springer.com/article/10.1007/s00224-022-10104-w | - |
| dc.identifier.uri | https://dlib.phenikaa-uni.edu.vn/handle/PNK/7379 | - |
| dc.description | CC BY | vi |
| dc.description.abstract | 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. | vi |
| dc.language.iso | en | vi |
| dc.publisher | Springer | vi |
| dc.subject | input digraph G = (V,A) | vi |
| dc.subject | NP-hard problem | vi |
| dc.title | Characterizations and Directed Path-Width of Sequence Digraphs | vi |
| dc.type | Book | vi |
| Bộ sưu tập | ||
| OER - Công nghệ thông tin | ||
Danh sách tệp tin đính kèm:
