A parallelizable lexicographically first maximal edge-induced subgraph problem

DOI10.1016/0020-0190(88)90095-6MaRDI QIDQ1108808zbMATH OpenOpenAlexFDO

Authors 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-freeNCouterplanar3-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)

Cites work

• scientific article; zbMATH DE number 3917742 (Why is no real title available?)
• scientific article; zbMATH DE number 4047154 (Why is no real title available?)
• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Simulation of Parallel Random Access Machines by Circuits
• Steiner trees, partial 2–trees, and minimum IFI networks
• Tree-size bounded alternation

Cited in

(5)

• The lexicographically first topological order problem is NLOG-complete
• Using maximal independent sets to solve problems in parallel
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• scientific article; zbMATH DE number 562727 (Why is no real title available?)
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems

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

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