The vertex separation and search number of a graph

DOI10.1006/inco.1994.1064zbMath0942.68641OpenAlexW2076322499WikidataQ29039022 ScholiaQ29039022MaRDI QIDQ1333276

V. Pereyra

Publication date: 26 February 1996

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/704a7c47a7b3d9f9763c1bf0e4125aa2267b00dd

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (92)

Refinements on an enumeration scheme for solving a pattern sequencing problem ⋮ Bounding the search number of graph products ⋮ Obstruction set isolation for the gate matrix layout problem ⋮ DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS ⋮ Approximating the pathwidth of outerplanar graphs ⋮ Memory requirements for table computations in partial k-tree algorithms ⋮ The pathwidth and treewidth of cographs ⋮ Obstructions to within a few vertices or edges of acyclic ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Decontamination of hypercubes by mobile agents ⋮ Combining intensification and diversification strategies in VNS. An application to the vertex separation problem ⋮ Variable neighborhood search for the vertex separation problem ⋮ Characterizing width two for variants of treewidth ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Computing the vertex separation of unicyclic graphs ⋮ Integer programming models and algorithms for the graph decontamination problem with mobile agents ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Locating a robber with multiple probes ⋮ On the thinness and proper thinness of a graph ⋮ Approximate search strategies for weighted trees ⋮ Outerplanar obstructions for matroid pathwidth ⋮ Fugitive-search games on graphs and related parameters ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Separating layered treewidth and row treewidth ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Order Reconfiguration under Width Constraints ⋮ How to hunt an invisible rabbit on a graph ⋮ Edge searching and fast searching with constraints ⋮ The complexity of zero-visibility cops and robber ⋮ Graph Searching in a Crime Wave ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ Pathwidth of Circular-Arc Graphs ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ On the thinness of trees ⋮ Interval degree and bandwidth of a graph ⋮ A distributed algorithm for computing the node search number in trees ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ Unnamed Item ⋮ Tradeoffs in process strategy games with application in the WDM reconfiguration problem ⋮ INTRUDER CAPTURING IN MESH AND TORUS NETWORKS ⋮ On partitioning a graph into two connected subgraphs ⋮ Three-fast-searchable graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Monotonicity of non-deterministic graph searching ⋮ The role of information in the cop-robber game ⋮ An annotated bibliography on guaranteed graph searching ⋮ Excluded Forest Minors and the Erdős–Pósa Property ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ PATH-WIDTH OF A GRAPH VS BRIDGE NUMBER OF A KNOT ⋮ Narrowness, pathwidth, and their application in natural language processing ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Neighbourhood-width of trees ⋮ Intervalizing k-colored graphs ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Four-searchable biconnected outerplanar graphs ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ The vertex separation number of a graph equals its path-width ⋮ Exclusive graph searching ⋮ PATHWIDTH AND LAYERED DRAWINGS OF TREES ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Fugitive-search games on graphs and related parameters ⋮ Unnamed Item ⋮ Finite graph automata for linear and boundary graph languages ⋮ A polynomial algorithm for recognizing bounded cutwidth in hypergraphs ⋮ Contiguous search problem in Sierpiński graphs ⋮ CSP duality and trees of bounded pathwidth ⋮ Minimal trees of given search number ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Tree-decompositions of small pathwidth ⋮ Monotony properties of connected visible graph searching ⋮ Graph classes and the switch Markov chain for matchings ⋮ On the domination search number ⋮ Sequentialization and procedural complexity in automata networks ⋮ Horton-Strahler number, rooted pathwidth and upward drawings of trees ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ Edge searching weighted graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Edge and node searching problems on trees ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ Interval graphs and searching ⋮ Zero-visibility cops and robber and the pathwidth of a graph ⋮ Non-deterministic graph searching in trees ⋮ Linear rank-width and linear clique-width of trees ⋮ Searching expenditure and interval graphs ⋮ Parameterized complexity of \((A,\ell)\)-path packing

This page was built for publication: The vertex separation and search number of a graph