Edge Search Number of Cographs in Linear Time

DOI10.1007/978-3-642-02270-8_5zbMath1248.05200OpenAlexW1538049091MaRDI QIDQ5321690

Rodica Mihai, Pinar Heggernes

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_5

zbMATH Keywords

linear time algorithmcographspolynomial timepermutation graphsedge search number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Bounding the search number of graph products ⋮ Edge search number of cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the vertex separation of unicyclic graphs
• Mixed searching and proper-path-width
• Monotonicity of non-deterministic graph searching
• An annotated bibliography on guaranteed graph searching
• Nondeterministic graph searching: from pathwidth to treewidth
• Interval graphs and searching
• Complement reducible graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the pathwidth of chordal graphs
• Some generalizations of the problem on the search number of a graph
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• The theory of search games and rendezvous.
• Edge and node searching problems on trees
• Graph searching on some subclasses of chordal graphs
• A simple linear time algorithm for cograph recognition
• Searching and pebbling
• Algorithmic graph theory and perfect graphs
• Node-searching problem on block graphs
• Mixed Search Number of Permutation Graphs
• Pathwidth of Circular-Arc Graphs
• Mixed Search Number and Linear-Width of Interval and Split Graphs
• Lower Bounds on Edge Searching
• Searching Cycle-Disjoint Graphs
• A Linear Recognition Algorithm for Cographs
• The complexity of searching a graph
• Monotonicity in graph searching
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Graph Classes: A Survey
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• Recontamination does not help to search a graph
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Edge Search Number of Cographs in Linear Time