Tradeoffs in process strategy games with application in the WDM reconfiguration problem

DOI10.1016/j.tcs.2011.05.002zbMath1386.91033OpenAlexW2049230986MaRDI QIDQ638539

Nathann Cohen, David Coudert, Napoleão Nepomuceno, Dorian Mazauric, Nicolas Nisse

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.002

zbMATH Keywords

graph searching gamesprocess numberrouting reconfiguration problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the monotonicity of process number, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• Graph minors. I. Excluding a forest
• The vertex separation and search number of a graph
• Approximating minimum feedback sets and multicuts in directed graphs
• Searching and pebbling
• Characterization of graphs and digraphs with small process numbers
• A distributed algorithm for computing the node search number in trees
• The complexity of searching a graph
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem