Clique partitions, graph compression and speeding-up algorithms

DOI10.1006/JCSS.1995.1065zbMATH Open0831.68073OpenAlexW1972978715MaRDI QIDQ1900930FDOQ1900930

Authors: Tomás Feder, Rajeev Motwani 

Publication date: 25 October 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1065

Recommendations

• The clique-partitioning problem
• Simple efficient graph compression schemes for dense and complement graphs
• Revisiting decomposition by clique separators
• scientific article; zbMATH DE number 1555964
• Algorithms for dense graphs and networks on the random access computer

zbMATH Keywords

graph partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cited In (38)

• Linear time approximation algorithms for~degree~constrained subgraph problems
• An improved approximation algorithm for the partial Latin square extension problem.
• On counting point-hyperplane incidences
• The maximum clique problem
• Path factors and parallel knock-out schemes of almost claw-free graphs
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Vertex disjoint paths on clique-width bounded graphs
• Parallel algorithms for bipartite matching problems on distributed memory computers
• A network game with attackers and a defender
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Speeding up Graph Algorithms via Switching Classes
• Properties of vector embeddings in social networks
• Compact structure for sparse undirected graphs based on a clique graph partition
• Distance-preserving subgraphs of interval graphs
• View disassembly: A rewrite that extracts portions of views
• Title not available (Why is that?)
• Representation complexities of semialgebraic graphs
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• Linear-time approximation for maximum weight matching
• Title not available (Why is that?)
• A simple reduction from maximum weight matching to maximum cardinality matching
• Algorithms for unipolar and generalized split graphs
• Graph compression by BFS
• A scaling algorithm for maximum weight matching in bipartite graphs
• Algorithms for dense graphs and networks on the random access computer
• Approximate labelled subtree homeomorphism
• Succinct posets
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• A fast scaling algorithm for the weighted triangle-free 2-matching problem
• An information-theoretic framework for the lossy compression of link streams
• Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights
• Covering a tree by a forest
• Title not available (Why is that?)
• Clique Cover and Graph Separation
• Maximum Steiner connected \(k\)-core query processing based on graph compression
• Faster algorithms for half-integral \(T\)-path packing

This page was built for publication: Clique partitions, graph compression and speeding-up algorithms

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