Characterization of graphs and digraphs with small process numbers

DOI10.1016/j.dam.2011.03.010zbMath1223.05297OpenAlexW2152871123MaRDI QIDQ2275910

Jean-Sébastien Sereni, David Coudert

Publication date: 10 August 2011

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

Full work available at URL: https://hal.inria.fr/inria-00587717/file/dam-noformat.pdf

zbMATH Keywords

pathwidthprocess numberreroutingvertex separation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

On the monotonicity of process number ⋮ A distributed algorithm for computing the node search number in trees ⋮ Tradeoffs in process strategy games with application in the WDM reconfiguration problem ⋮ Characterization of graphs and digraphs with small process numbers ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• Graph minors. I. Excluding a forest
• Quickly excluding a forest
• The vertex separation number of a graph equals its path-width
• Graph searching and a min-max theorem for tree-width
• Obstruction set isolation for the gate matrix layout problem
• On the solution of reroute sequence planning problem in MPLS networks.
• Characterization of graphs and digraphs with small process numbers
• Rerouting tunnels for MPLS network resource optimization
• The complexity of searching a graph
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• Robust linear algorithms for cutsets
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Characterization of graphs and digraphs with small process numbers