Computing the zig-zag number of directed graphs

DOI10.1016/j.dam.2021.09.013zbMath1485.05072OpenAlexW3202990525MaRDI QIDQ831867

Mateus de Oliveira Oliveira, Uéverton S. Souza, Alexsander A. de Melo, Mitre C. Dourado, Celina M. Herrera de Figueiredo

Publication date: 24 March 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.09.013

zbMATH Keywords

computational complexityNP-completenessdirected graphsdirected width measurezig-zag number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• An algorithmic metatheorem for directed treewidth
• The dag-width of directed graphs
• Are there any good digraph width measures?
• Digraph measures: Kelly decompositions, games, and orderings
• Digraph searching, directed vertex separation and directed pathwidth
• A partial k-arboretum of graphs with bounded treewidth
• Directed tree-width
• Entanglement and the complexity of directed graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Directed path-width and monotonicity in digraph searching
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• On Digraph Width Measures in Parameterized Algorithmics
• Hamilton Paths in Grid Graphs
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2005