Mixed searching and proper-path-width

DOI10.1016/0304-3975(94)00160-KzbMath0873.68148MaRDI QIDQ674341

Yoji Kajitani, Shuichi Ueno, Atsushi Takahashi

Publication date: 28 February 1997

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Throttling for Zero Forcing and Variants, On the Cooperative Graph Searching Problem, Strong-mixed searching and pathwidth, Edge Search Number of Cographs in Linear Time, Lower bounds for protrusion replacement by counting equivalence classes, Parameterized orientable deletion, Mixed Search Number of Permutation Graphs, Edge search number of cographs, Graph Searching in a Crime Wave, Mixed Search Number and Linear-Width of Interval and Split Graphs, The mixed search game against an agile and visible fugitive is monotone, On the monotonicity of games generated by symmetric submodular functions., An annotated bibliography on guaranteed graph searching, Mixed searching and proper-path-width, Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph, Minimum dominating set of queens: a trivial programming exercise?, Embeddings of \(k\)-connected graphs of pathwidth \(k\), Mixed search number and linear-width of interval and split graphs, On the number of labeled graphs of bounded treewidth, On the parameterized complexity of \([1,j\)-domination problems], Minimum reload cost graph factors, On the Parameterized Complexity of [1,j-Domination Problems], A partial k-arboretum of graphs with bounded treewidth, Structurally parameterized \(d\)-scattered set, Searching for a Visible, Lazy Fugitive, Finding small-width connected path decompositions in polynomial time, Algorithms and obstructions for linear-width and related search parameters, Pure Nash equilibria in graphical games and treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixed searching and proper-path-width
• Graph minors. XX: Wagner's conjecture
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Searching and pebbling
• Graph minors. XIII: The disjoint paths problem
• Complexity of Finding Embeddings in a k-Tree
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• The NP-completeness column: An ongoing guide