An efficiently solvable graph partition problem to which many problems are reducible

DOI10.1016/0020-0190(93)90038-BMaRDI QIDQ2365814zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

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

zbMATH Keywords

2-CNFSAT2-colors graph partition2-QBF Truthbipartite graphsNLOGSPACEparallel algorithmsrecognition problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Restrictions of graph partition problems. I
• Serial and parallel algorithms for \((k,2)\)-partite graphs
• Between 2- and 3-colorability
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• The Complexity of the List Partition Problem for Graphs

Cites work

• A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A practical algorithm for Boolean matrix multiplication
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• New problems complete for nondeterministic log space
• Nondeterministic Space is Closed under Complementation
• On chain and antichain families of a partially ordered set
• On the Complexity of Timetable and Multicommodity Flow Problems
• Testing for Equality between Maximum Matching and Minimum Node Covering

Cited in

(10)

• Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling
• Tree partitioning under constraints. -- Clustering for vehicle routing problems
• Note on maximal split-stable subgraphs
• On approximability of optimization problems related to red/blue-split graphs
• Bipartite bihypergraphs: a survey and new results
• On some conjectures concerning critical independent sets of a graph
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• On 2-QBF truth testing in parallel
• Rainbow graph splitting
• Solving partition problems with colour-bipartitions

This page was built for publication: An efficiently solvable graph partition problem to which many problems are reducible

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