Characterization of graphs and digraphs with small process numbers

DOI10.1016/j.dam.2011.03.010zbMath1223.05297MaRDI 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

pathwidth; process number; rerouting; vertex separation

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

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

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