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

3-cycle free edge-induced subgraphmaximal subgraph problemNCouterplanartriangle-free

Mathematics Subject Classification ID

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

Review text

The lexicographically first maximal 3-cycle free edge-induced subgraph problem is in \(NC^ 2\) when the instances are graphs without any subgraphs homeomorphic to \(K_ 4\).

Cites work

• A taxonomy of problems with fast parallel algorithms
• 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?)
• Simulation of Parallel Random Access Machines by Circuits
• Steiner trees, partial 2–trees, and minimum IFI networks
• Tree-size bounded alternation

Cited in

(5)

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

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)