Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search

DOI10.1051/ita/2010016zbMath1210.68132MaRDI QIDQ3060200

Siang W. Song, Jayme Luiz Szwarcfiter, E. N. Cáceres

Publication date: 1 December 2010

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2010__44_3_293_0/

zbMATH Keywords

maximal clique; PRAM algorithm; circle graph; BSP/CGM algorithm; unrestricted depth search

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Cites Work

• Practical and efficient circle graph recognition
• A parallel search algorithm for directed acyclic graphs
• Reconnaissance des graphes de cordes
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Reducing prime graphs and recognizing circle graphs
• Special issue: Coarse-grained parallel algorithms
• Efficient parallel graph algorithms for coarse-grained multicomputers and BSP
• Arboricity and Subgraph Listing Algorithms
• Fast Parallel Algorithms for Chordal Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Efficient Parallel Algorithms for Chordal Graphs
• Algorithm Theory - SWAT 2004
• Depth-First Search and Linear Graph Algorithms
• On cliques in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item