Searching and pebbling

From MaRDI portal
Revision as of 09:47, 1 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:1821562

DOI10.1016/0304-3975(86)90146-5zbMath0616.68064OpenAlexW2015469394WikidataQ29030357 ScholiaQ29030357MaRDI QIDQ1821562

Lefteris M. Kirousis, Christos H. Papadimitriou

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90146-5




Related Items (only showing first 100 items - show all)

Complexity and monotonicity results for domination gamesSearching for an evader in an unknown dark cave by an optimal number of asynchronous searchersIntruder alert! Optimization models for solving the mobile robot graph-clear problemImproved self-reduction algorithms for graphs with bounded treewidthA polynomial time algorithm to compute the connected treewidth of a series-parallel graphNETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITYDECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTSFinding hidden independent sets in interval graphsOn the monotonicity of process numberDecontamination of hypercubes by mobile agentsCombining intensification and diversification strategies in VNS. An application to the vertex separation problemA simple method for proving lower bounds in the zero-visibility cops and robber gameVariable neighborhood search for the vertex separation problemJumping robbers in digraphsMin Cut is NP-complete for edge weighted treesStrong-mixed searching and pathwidthComputing the vertex separation of unicyclic graphsThe Complexity of the Positive Semidefinite Zero ForcingOn minimum cost edge searchingApproximate search strategies for weighted treesFast-mixed searching and related problems on graphsFugitive-search games on graphs and related parametersHelicopter search problems, bandwidth and pathwidthHow to hunt an invisible rabbit on a graphFast searching games on graphsMixed Search Number of Permutation GraphsThe complexity of zero-visibility cops and robberEdge search number of cographsMonotonicity of Non-deterministic Graph SearchingThe mixed search game against an agile and visible fugitive is monotoneMonotonicity of strong searching on digraphsConnections between cutting-pattern sequencing, VLSI design, and flexible machinesA distributed algorithm for computing the node search number in treesFast edge searching and fast searching on graphsOn the monotonicity of games generated by symmetric submodular functions.Network decontamination under \(m\)-immunityFast searching on cactus graphsTradeoffs in process strategy games with application in the WDM reconfiguration problemThe dag-width of directed graphsThe theory of guaranteed search on graphsINTRUDER CAPTURING IN MESH AND TORUS NETWORKSUnnamed ItemUnnamed ItemThree-fast-searchable graphsFast Searching on Cartesian Products of GraphsMonotonicity of non-deterministic graph searchingAn annotated bibliography on guaranteed graph searchingDistributed chasing of network intrudersApproximation algorithms for digraph width parametersUnnamed ItemQuickly excluding a forestThe complexity of minimum-length path decompositionsNode-searching problem on block graphsNarrowness, pathwidth, and their application in natural language processingDigraph searching, directed vertex separation and directed pathwidthON mRJ REACHABILITY IN TREESMixed searching and proper-path-widthLower bounds for positive semidefinite zero forcing and their applicationsMonotonicity in digraph search problemsThe vertex separation number of a graph equals its path-widthExclusive graph searchingLower bounds on the pathwidth of some grid-like graphsThe fast search number of a Cartesian product of graphsConnected graph searchingOn tradeoffs between width- and fill-like graph parametersStep-wise tile assembly with a constant number of tile typesSearch and sweep numbers of finite directed acyclic graphsConnected graph searching in chordal graphsA graph search algorithm for indoor pursuit/evasionFinite graph automata for linear and boundary graph languagesThe treewidth of proofsLIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depthContiguous search problem in Sierpiński graphsCSP duality and trees of bounded pathwidthMaximum vertex occupation time and inert fugitive: Recontamination does helpConnected searching of weighted treesOn reachability in graphs with obstaclesExclusive graph searching vs. pathwidthMonotony properties of connected visible graph searchingA property of random walks on a cycle graphOn the domination search numberLIFO-Search on Digraphs: A Searching Game for Cycle-RankNondeterministic graph searching: from pathwidth to treewidthEdge searching weighted graphsA partial k-arboretum of graphs with bounded treewidthStandard directed search strategies and their applicationsA two-person game on graphs where each player tries to encircle his opponent's menOn Rerouting Connection Requests in Networks with Shared BandwidthEdge and node searching problems on treesOne-visibility cops and robber on trees: optimal cop-win strategiesFinding small-width connected path decompositions in polynomial timeSweeping graphs with large clique numberComputing the chromatic number using graph decompositions via matrix rankAlgorithms and obstructions for linear-width and related search parametersDirected tree-widthInterval graphs and searchingOn the pathwidth of chordal graphsLinear rank-width and linear clique-width of treesSearching expenditure and interval graphsThe searchlight problem for road networks




Cites Work




This page was built for publication: Searching and pebbling