Edge search number of cographs

DOI10.1016/j.dam.2011.04.020zbMath1238.68107MaRDI QIDQ415273

Rodica Mihai, Pinar Heggernes, Petr A. Golovach

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.04.020

zbMATH Keywords

polynomial-time algorithm; cographs; NP-hard problem; graph classes; graph searching

Mathematics Subject Classification ID

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Exclusive graph searching, Exclusive graph searching vs. pathwidth, Complete edge-colored permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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
• 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
• Edge Search Number of Cographs in Linear Time
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Mathematical Foundations of Computer Science 2005
• Graph-Theoretic Concepts in Computer Science