Competitive graph searches

DOI10.1016/j.tcs.2007.10.048zbMath1136.68040OpenAlexW2011243986MaRDI QIDQ2481952

Christophe Paul, Binh-Minh Bui-Xuan, Michel A. Habib

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00132103/file/BHP07.pdf

zbMATH Keywords

graph searchdivide-and-conquer algorithmcommon connected graph componentsandwich graph problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Assessing the Computational Complexity of Multi-layer Subgraph Detection ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Complexity issues for the sandwich homogeneous set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• An algorithmic view of gene teams
• The pair completion algorithm for the homogeneous set sandwich problem
• Partitive hypergraphs
• Fast algorithms to enumerate all common intervals of two permutations
• Fast algorithms for identifying maximal common connected sets of interval graphs
• On a property of the class of n-colorable graphs
• Solution of a Divide-and-Conquer Maximin Recurrence
• Applications of a Planar Separator Theorem
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Multidimensional Divide-and-Conquer Maximin Recurrences
• Graph Sandwich Problems
• Algorithms – ESA 2005
• Algorithms and Computation

This page was built for publication: Competitive graph searches