An efficiently solvable graph partition problem to which many problems are reducible
From MaRDI portal
Publication:2365814
DOI10.1016/0020-0190(93)90038-BzbMath0768.68140OpenAlexW2089719371MaRDI QIDQ2365814
Publication date: 29 June 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90038-b
parallel algorithmsbipartite graphsrecognition problem2-CNFSAT2-colors graph partition2-QBF TruthNLOGSPACE
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (9)
On some conjectures concerning critical independent sets of a graph ⋮ Note on maximal split-stable subgraphs ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ On 2-QBF truth testing in parallel ⋮ Bipartite bihypergraphs: a survey and new results ⋮ Rainbow graph splitting ⋮ Solving partition problems with colour-bipartitions ⋮ Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling
Cites Work
- A practical algorithm for Boolean matrix multiplication
- On chain and antichain families of a partially ordered set
- A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
- Testing for Equality between Maximum Matching and Minimum Node Covering
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Algorithms for maximumk-colorings andk-coverings of transitive graphs
- Nondeterministic Space is Closed under Complementation
- New problems complete for nondeterministic log space
- On the Complexity of Timetable and Multicommodity Flow Problems
This page was built for publication: An efficiently solvable graph partition problem to which many problems are reducible
