The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

DOI10.1007/BF02088292zbMATH Open0679.68090OpenAlexW1498460077MaRDI QIDQ4729355FDOQ4729355

Satoru Miyano

Publication date: 1989

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02088292

zbMATH Keywords

P-completenessNC algorithmslfm subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The node-deletion problem for hereditary properties is NP-complete
• On uniform circuit complexity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A taxonomy of problems with fast parallel algorithms
• Efficient Planarity Testing
• An observation on time-storage trade off
• Node-Deletion Problems on Bipartite Graphs
• Depth-first search is inherently sequential
• Complete problems for deterministic polynomial time
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Linear programming is log-space hard for P
• Parallelism and the maximal path problem
• A parallelizable lexicographically first maximal edge-induced subgraph problem
• Lower bounds on parallel algorithms for finding the first maximal independent set
• The Nielsen reduction and P-complete problems in free groups
• The maximum flow problem is log space complete for P

Cited In (9)

• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
• The parallel complexity of elimination ordering procedures
• On the Parameterized Parallel Complexity and the Vertex Cover Problem
• A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• Monadic second-order evaluations on tree-decomposable graphs
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Using maximal independent sets to solve problems in parallel

This page was built for publication: The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

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