Fast-mixed searching and related problems on graphs

DOI10.1016/j.tcs.2013.04.015zbMath1302.05197MaRDI 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

68Q25: Analysis of algorithms and problem complexity

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

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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