Searching and pebbling

1986/01/01 by Lefteris M. Kirousis, Christos H. Papadimitriou · 15 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Clearance #Combinatorics #Computer science #Data Management and Algorithms #Directed acyclic graph #Discrete mathematics #Graph #Mathematics #Node (physics) #Optimization and Search Problems #Pebble #Theoretical computer science #Undirected graph #Vertex (graph theory)

paper · doi:10.1016/0304-3975(86)90146-5

crossref issued 1986/01/01 · crossref published 1986/01/01 · crossref published-print 1986/01/01 · openalex publication_date 1986/01/01 · crossref created 2003/05/13 · crossref deposited 2019/03/21 · openalex created_date 2025/10/10 · crossref indexed 2026/06/03 · openalex updated_date 2026/07/23

Citations

• Black-white pebbles and graph separation

Cited by

• Finding approximate separators and computing tree width quickly
• Narrowness, pathwidth, and their application in natural language processing
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• On the pathwidth of chordal graphs
• Pathwidth of Planar and Line Graphs
• Directed Tree-Width
• Min cut is NP-complete for edge weighted trees
• The vertex separation number of a graph equals its path-width
• Graph Searching and a Min-Max Theorem for Tree-Width
• Interval graphs and seatching
• Memory Requirements for Table Computations in Partial \sl k -Tree Algorithms
• A Distributed Algorithm for Computing the Node Search Number in Trees
• Quickly excluding a forest
• Computing Optimal Linear Layouts of Trees in Linear Time
• The pathwidth and treewidth of cographs
• Pursuit–evasion [wikipedia]