The Library
Combinatorics and algorithms for quasi-chain graphs
Tools
Alecu, Bogdan, Atminas, Aistis, Lozin, Vadim V. and Malyshev, Dmitriy (2023) Combinatorics and algorithms for quasi-chain graphs. Algorithmica, 85 . 642-664 . doi:10.1007/s00453-022-01019-6 ISSN 0178-4617.
|
PDF
WRAP-Combinatorics-algorithms-Quasi-Chain-Graphs-22.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (487Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-022-01019-6
Abstract
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Bipartite graphs, Algorithms, Computer science -- Mathematics | ||||||||
Journal or Publication Title: | Algorithmica | ||||||||
Publisher: | Springer Verlag | ||||||||
ISSN: | 0178-4617 | ||||||||
Official Date: | March 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 85 | ||||||||
Page Range: | 642-664 | ||||||||
DOI: | 10.1007/s00453-022-01019-6 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 15 August 2022 | ||||||||
Date of first compliant Open Access: | 15 August 2022 | ||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year