Edge search number of cographs

DOI10.1016/J.DAM.2011.04.020MaRDI QIDQ415273zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Pinar Heggernes, Rodica Mihai

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

graph classespolynomial-time algorithmcographsgraph searchingNP-hard problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Recommendations

• Edge Search Number of Cographs in Linear Time
• Edge search in hypergraphs
• Edge-domatic number of a graph
• Edge search in graphs and hypergraphs of bounded rank
• The edge numbers of a class of graphs
• scientific article; zbMATH DE number 846942
• Total edge-domatic number of a graph
• scientific article; zbMATH DE number 3993644
• scientific article; zbMATH DE number 4105017
• An NP-completeness result of edge search in graphs

Cites work

• scientific article; zbMATH DE number 4174651 (Why is no real title available?)
• scientific article; zbMATH DE number 4202053 (Why is no real title available?)
• scientific article; zbMATH DE number 4154499 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A simple linear time algorithm for cograph recognition
• Algorithmic graph theory and perfect graphs
• An annotated bibliography on guaranteed graph searching
• Complement reducible graphs
• Computing the vertex separation of unicyclic graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Edge Search Number of Cographs in Linear Time
• Edge and node searching problems on trees
• Graph Classes: A Survey
• Graph searching on some subclasses of chordal graphs
• Graph-Theoretic Concepts in Computer Science
• Interval graphs and searching
• Lower Bounds on Edge Searching
• Mathematical Foundations of Computer Science 2005
• Mixed Search Number and Linear-Width of Interval and Split Graphs
• Mixed Search Number of Permutation Graphs
• Mixed searching and proper-path-width
• Monotonicity in graph searching
• Monotonicity of non-deterministic graph searching
• Node-searching problem on block graphs
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• On the pathwidth of chordal graphs
• Pathwidth of Circular-Arc Graphs
• Recontamination does not help to search a graph
• Searching Cycle-Disjoint Graphs
• Searching and pebbling
• Some generalizations of the problem on the search number of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Pathwidth and Treewidth of Cographs
• The complexity of searching a graph
• The theory of search games and rendezvous.
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(5)

• Edge Search Number of Cographs in Linear Time
• Complete edge-colored permutation graphs
• Mixed Search Number of Permutation Graphs
• Exclusive graph searching
• Exclusive graph searching vs. pathwidth

This page was built for publication: Edge search number of cographs

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