Fast-mixed searching and related problems on graphs

DOI10.1016/j.tcs.2013.04.015zbMath1302.05197OpenAlexW1991356098MaRDI QIDQ393051

Boting Yang

Publication date: 16 January 2014

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (34)

Throttling for Zero Forcing and Variants ⋮ Computational approaches for zero forcing and related problems ⋮ Positive Semidefinite Zero Forcing: Complexity and Lower Bounds ⋮ k-Forcing number for Cartesian product of some graphs ⋮ Compressed cliques graphs, clique coverings and positive zero forcing ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Throttling processes equivalent to full throttling on trees ⋮ The Complexity of the Positive Semidefinite Zero Forcing ⋮ Minimum rank and zero forcing number for butterfly networks ⋮ On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme ⋮ Connected power domination in graphs ⋮ On graphs maximizing the zero forcing number ⋮ Infection in hypergraphs ⋮ Throttling positive semidefinite zero forcing propagation time on graphs ⋮ Zero forcing in iterated line digraphs ⋮ Positive Zero Forcing and Edge Clique Coverings ⋮ A New Lower Bound for Positive Zero Forcing ⋮ Properties of a \(q\)-analogue of zero forcing ⋮ The zero forcing polynomial of a graph ⋮ Bounds on expected propagation time of probabilistic zero forcing ⋮ Lower bounds for positive semidefinite zero forcing and their applications ⋮ Brushing number and zero-forcing number of graphs and their line graphs ⋮ The fast search number of a Cartesian product of graphs ⋮ Propagation time for probabilistic zero forcing ⋮ Rigid linkages and partial zero forcing ⋮ Complexity and computation of connected zero forcing ⋮ On the relationships between zero forcing numbers and certain graph coverings ⋮ On the complexity of failed zero forcing ⋮ On the complexity of the positive semidefinite zero forcing number ⋮ Skew throttling ⋮ Unnamed Item ⋮ Positive semidefinite zero forcing numbers of two classes of graphs ⋮ Product throttling ⋮ Using Markov chains to determine expected propagation time for probabilistic zero forcing

Cites Work

• Unnamed Item
• Unnamed Item
• Fast searching games on graphs
• Fast edge searching and fast searching on graphs
• Induced-path partition on graphs with special blocks
• Interval graphs and interval orders
• Optimal covering of cacti by vertex-disjoint paths
• Splitting a graph into disjoint induced paths or cycles.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Searching and pebbling
• On the Fast Searching Problem
• Minimum-weight triangulation is NP-hard
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph

This page was built for publication: Fast-mixed searching and related problems on graphs