Interval graphs and searching
From MaRDI portal
Publication:1059088
DOI10.1016/0012-365X(85)90046-9zbMath0566.05056MaRDI QIDQ1059088
Christos H. Papadimitriou, Lefteris M. Kirousis
Publication date: 1985
Published in: Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, The pathwidth and treewidth of cographs, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Variable neighborhood search for the vertex separation problem, Jumping robbers in digraphs, Edge Search Number of Cographs in Linear Time, Computing the vertex separation of unicyclic graphs, Approximate search strategies for weighted trees, Fugitive-search games on graphs and related parameters, Helicopter search problems, bandwidth and pathwidth, Connected search for a lazy robber, How to hunt an invisible rabbit on a graph, Mixed Search Number of Permutation Graphs, The complexity of zero-visibility cops and robber, Edge search number of cographs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Connections between cutting-pattern sequencing, VLSI design, and flexible machines, Unnamed Item, Interval degree and bandwidth of a graph, On the monotonicity of games generated by symmetric submodular functions., The theory of guaranteed search on graphs, Searching with mobile agents in networks with liars., Imbalance is fixed parameter tractable, An annotated bibliography on guaranteed graph searching, Distributed chasing of network intruders, Quickly excluding a forest, The complexity of minimum-length path decompositions, Node-searching problem on block graphs, Narrowness, pathwidth, and their application in natural language processing, Mixed searching and proper-path-width, Excluding infinite minors, A 3-approximation for the pathwidth of Halin graphs, The vertex separation number of a graph equals its path-width, Connected graph searching, On tradeoffs between width- and fill-like graph parameters, Fugitive-search games on graphs and related parameters, Step-wise tile assembly with a constant number of tile types, The inverse Voronoi problem in graphs. I: Hardness, Finite graph automata for linear and boundary graph languages, On the interval completion of chordal graphs, Maximum vertex occupation time and inert fugitive: Recontamination does help, Mixed search number and linear-width of interval and split graphs, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Metric dimension parameterized by treewidth, A partial k-arboretum of graphs with bounded treewidth, Searching for a Visible, Lazy Fugitive, Edge and node searching problems on trees, Algorithms and obstructions for linear-width and related search parameters, Hardness of metric dimension in graphs of constant treewidth, Directed tree-width, Interval graphs and related topics, On the pathwidth of chordal graphs, Zero-visibility cops and robber and the pathwidth of a graph, Parameterized complexity of \((A,\ell)\)-path packing
Cites Work
