Digraph searching, directed vertex separation and directed pathwidth

DOI10.1016/j.dam.2007.08.045zbMath1152.05331OpenAlexW1989886714MaRDI QIDQ944735

Boting Yang, Yi Cao

Publication date: 10 September 2008

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

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

zbMATH Keywords

directed pathwidthdirected searchdigraph searchingdirected vertex separationstrong searchundirected searchweak search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (15)

Computing the zig-zag number of directed graphs ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ On the Pathwidth of Almost Semicomplete Digraphs ⋮ Characterizations and directed path-width of sequence digraphs ⋮ Monotonicity of strong searching on digraphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Monotonicity in digraph search problems ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Controlling distribution conveyors and multiline palletizers: theoretical foundations and online algorithms ⋮ Sequentialization and procedural complexity in automata networks ⋮ Standard directed search strategies and their applications ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ Comparing linear width parameters for directed graphs ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The vertex separation number of a graph equals its path-width
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Helicopter search problems, bandwidth and pathwidth
• Algorithms and obstructions for linear-width and related search parameters
• Graph searching, elimination trees, and a generalization of bandwidth
• Searching and pebbling
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Directed tree-width examples
• Graph Searching and Interval Completion
• DAG-width
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• Directed Searching Digraphs: Monotonicity and Complexity
• Digraph Strong Searching: Monotonicity and Complexity
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Digraph searching, directed vertex separation and directed pathwidth