A parallelizable lexicographically first maximal edge-induced subgraph problem

DOI10.1016/0020-0190(88)90095-6zbMath0654.68085OpenAlexW2078777386MaRDI QIDQ1108808

Satoru Miyano

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90095-6

zbMATH Keywords

triangle-freeouterplanarNC3-cycle free edge-induced subgraphmaximal subgraph problem

Mathematics Subject Classification ID

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

Related Items (4)

\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Using maximal independent sets to solve problems in parallel ⋮ The lexicographically first topological order problem is NLOG-complete ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

Cites Work

• Tree-size bounded alternation
• Steiner trees, partial 2–trees, and minimum IFI networks
• Simulation of Parallel Random Access Machines by Circuits
• A taxonomy of problems with fast parallel algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A parallelizable lexicographically first maximal edge-induced subgraph problem