A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS

DOI10.1142/S0129054199000332zbMath1319.68114MaRDI QIDQ5249021

Ryuhei Uehara

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithmsP-completenessNC algorithmslexicographically first maximal subgraph problemsthreshold function of a random graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Unnamed Item

Cites Work

• Using maximal independent sets to solve problems in parallel
• Parallel graph algorithms that are efficients on average
• A taxonomy of problems with fast parallel algorithms
• A fast parallel algorithm for the maximal independent set problem
• Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

This page was built for publication: A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS