Computing small search numbers in linear time

DOI10.1007/978-3-540-28639-4_4MaRDI QIDQ5311524zbMATH OpenOpenAlexFDO

Authors Dimitrios M. Thilikos, Hans L. Bodlaender

Publication date 23 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100584, https://dspace.library.uu.nl/handle/1874/18909

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Algorithms and obstructions for linear-width and related search parameters
• Mixed search number and linear-width of interval and split graphs
• scientific article; zbMATH DE number 176249
• Fast-mixed searching on graphs
• SOFSEM 2006: Theory and Practice of Computer Science

Cited in

(18)

• Algorithms and obstructions for linear-width and related search parameters
• Lower bounds on the pathwidth of some grid-like graphs
• Typical sequences revisited -- computing width parameters of graphs
• Computing optimal linear layouts of trees in linear time
• Contraction obstructions for connected graph searching
• Mixed search number and linear-width of interval and split graphs
• Pathwidth and searching in parameterized threshold graphs
• A linear-time algorithm for constructing an optimal node-search strategy of a tree
• Confronting intractability via parameters
• The Linkage of a Graph
• A linear fixed parameter tractable algorithm for connected pathwidth
• Edge Search Number of Cographs in Linear Time
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Edge-treewidth: algorithmic and combinatorial properties
• Connected graph searching
• Monotonicity of the cops and robber game for bounded depth treewidth
• On minimizing width in linear layouts
• An annotated bibliography on guaranteed graph searching

This page was built for publication: Computing small search numbers in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311524)