Computing the zig-zag number of directed graphs

DOI10.1016/J.DAM.2021.09.013MaRDI QIDQ831867zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, Alexsander A. de Melo, Mateus de Oliveira Oliveira, Uéverton S. Souza, Celina M. H. 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

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

Recommendations

• An algorithmic metatheorem for directed treewidth
• scientific article; zbMATH DE number 1161355
• scientific article; zbMATH DE number 2188410
• The burning number of directed graphs: bounds and computational complexity
• Jump number of dags having Dilworth number 2

Cites work

• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• A partial k-arboretum of graphs with bounded treewidth
• An algorithmic metatheorem for directed treewidth
• Are there any good digraph width measures?
• Digraph measures: Kelly decompositions, games, and orderings
• Digraph searching, directed vertex separation and directed pathwidth
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Entanglement and the complexity of directed graphs
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Hamilton Paths in Grid Graphs
• Introducing directed tree width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Mathematical Foundations of Computer Science 2005
• On digraph width measures in parameterized algorithmics
• Subgraphs satisfying MSO properties on \(z\)-topologically orderable digraphs
• The complexity of satisfiability problems
• The dag-width of directed graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Computing the zig-zag number of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831867)