Item Infomation
Title: | Characterizations and Directed Path-Width of Sequence Digraphs |
Authors: | Frank, Gurski Carolin, Rehs Jochen, Rethmann |
Issue Date: | 2023 |
Publisher: | Springer |
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. |
Description: | CC BY |
URI: | https://link.springer.com/article/10.1007/s00224-022-10104-w https://dlib.phenikaa-uni.edu.vn/handle/PNK/7379 |
Appears in Collections | OER - Công nghệ thông tin |
ABSTRACTS VIEWS
31
FULLTEXT VIEWS
3
Files in This Item: