Edge Search Number of Cographs in Linear Time

DOI10.1007/978-3-642-02270-8_5MaRDI QIDQ5321690zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Rodica Mihai

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

cographsedge search numberlinear time algorithmpermutation graphspolynomial time

Mathematics Subject Classification ID

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

Recommendations

• Edge search number of cographs
• Parameterized and Exact Computation
• scientific article; zbMATH DE number 3896983
• A simple linear time algorithm for cograph recognition
• A Linear Recognition Algorithm for Cographs

Cites work

• 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 and node searching problems on trees
• Graph Classes: A Survey
• Graph searching on some subclasses of chordal graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 4174651 (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?)
• Interval graphs and searching
• Lower Bounds on Edge Searching
• 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
• Nondeterministic graph searching: from pathwidth to treewidth
• On the pathwidth of chordal graphs
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Pathwidth of Circular-Arc Graphs
• Recontamination does not help to search a graph
• Searching and pebbling
• Searching Cycle-Disjoint Graphs
• 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 complexity of searching a graph
• The Pathwidth and Treewidth of Cographs
• The theory of search games and rendezvous.
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(3)

• An NP-completeness result of edge search in graphs
• Edge search number of cographs
• Bounding the search number of graph products

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

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