Computing the zig-zag number of directed graphs
type: Item
instance of: scholarly article
title: Computing the zig-zag number of directed graphs
zbMATH Open document ID: 1485.05072
author: Mitre C. Dourado
author: Alexsander A. de Melo
author: Mateus de Oliveira Oliveira
author: Uéverton S. Souza
author: Celina M. H. de Figueiredo
published in: Discrete Applied Mathematics
publication date: 2022-03-24T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 7497779
zbMATH Keywords: zig-zag number
zbMATH Keywords: directed graphs
zbMATH Keywords: directed width measure
zbMATH Keywords: NP-completeness
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.dam.2021.09.013
OpenAlex ID: W3202990525
cites work: Directed path-width and monotonicity in digraph searching
cites work: The dag-width of directed graphs
cites work: Entanglement and the complexity of directed graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: On Digraph Width Measures in Parameterized Algorithmics
cites work: Are there any good digraph width measures?
cites work: Finite Automata, Digraph Connectivity, and Regular Expression Size
cites work: Digraph measures: Kelly decompositions, games, and orderings
cites work: Hamilton Paths in Grid Graphs
cites work: Directed tree-width
cites work: Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
cites work: An algorithmic metatheorem for directed treewidth
cites work: Introducing directed tree width
cites work: Mathematical Foundations of Computer Science 2005
cites work: The complexity of satisfiability problems
cites work: A Polynomial Time Algorithm for Bounded Directed Pathwidth
cites work: Digraph searching, directed vertex separation and directed pathwidth
DOI: 10.1016/J.DAM.2021.09.013
description: scientific article; zbMATH DE number 7497779