An overview of graph covering and partitioning

DOI10.1016/j.disc.2022.112884zbMath1490.05220OpenAlexW4220901620MaRDI QIDQ2142633

Stephan Schwartz

Publication date: 27 May 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2022.112884

zbMATH Keywords

graph partitioningvertex coveringedge covering

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

An efficient heuristic for the \(k\)-partitioning problem ⋮ Vertex covering with capacitated trees ⋮ Political districting to minimize cut edges

Uses Software

• PERL
• MESHPART
• VRP
• MCODE

Cites Work

• A bound on the total size of a cut cover
• Fractional biclique covers and partitions of graphs
• The equipartition polytope. I: Formulations, dimension and basic facets
• The Vehicle Routing Problem
• An Optimization Based Heuristic for Political Districting
• Engineering Branch-and-Cut Algorithms for the Equicut Problem
• The Bounded Cycle-Cover Problem
• Solution of a Min-Max Vehicle Routing Problem
• Approximation algorithms for distance constrained vehicle routing problems
• FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
• More on the Bipartite Decomposition of Random Graphs
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Maximal Flow Through a Network
• Two exact algorithms for the distance-constrained vehicle routing problem
• Clique Covering of Graphs IV. Algorithms
• Path and cycle decompositions of dense graphs
• On the Graph Bisection Cut Polytope
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Local Clique Covering of Claw-Free Graphs
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• On Approximating Restricted Cycle Covers
• Optimal Routing under Capacity and Distance Restrictions
• Covering Multigraphs by Simple Circuits
• On partitioning the edges of graphs into connected subgraphs
• On Restricted Two-Factors
• Max-Min Tree Partitioning
• Covering Graphs by Simple Circuits
• Clique coverings of graphs V: maximal-clique partitions
• On the decomposition ofkn into complete bipartite graphs
• On the Distance Constrained Vehicle Routing Problem
• Clique-Web Facets for Multicut Polytopes
• An Efficient Heuristic Procedure for Partitioning Graphs
• A Linear Tree Partitioning Algorithm
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• The biparticity of a graph
• An upper bound for the path number of a graph
• Geometric Mesh Partitioning: Implementation and Experiments
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• On the hardness of approximating minimization problems
• A Cartesian Parallel Nested Dissection Algorithm
• On the Complexity of Finding a Minimum Cycle Cover of a Graph
• Variable Neighborhood Search
• The clique partitioning problem: Facets and patching facets
• Max-min partitioning of grid graphs into connected components
• Community structure in social and biological networks
• Edge clique cover of claw‐free graphs
• Partitioning a graph into connected components with fixed centers and optimizing cost‐based objective functions or equipartition criteria
• Matching, Euler tours and the Chinese postman
• A spanning tree heuristic for regional clustering
• Old Bachelor Acceptance: A New Class of Non-Monotone Threshold Accepting Methods
• Algorithms and Computation
• Coverability of graph by three odd subgraphs
• Decomposing Graphs into Edges and Triangles
• Clique Cover on Sparse Networks
• Data reduction and exact algorithms for clique cover
• Short Proofs of Some Extremal Results
• Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Covering the edges of a graph by three odd subgraphs
• Approximations for minimum and min-max vehicle routing problems
• Circuit Double Covers of Graphs
• The Representation of a Graph by Set Intersections
• Optimal Political Districting by Implicit Enumeration Techniques
• An r-Dimensional Quadratic Placement Algorithm
• STACS 2005
• Decomposition of Finite Graphs Into Forests
• Optimal Districting and Territory Design
• Municipal Solid Waste Collection: An Effective Data Structure For Solving The Sectorization Problem With Local Search Methods
• Approximation algorithms for maximally balanced connected graph partition
• New approximation algorithms for the rooted budgeted cycle cover problem
• New approximation algorithms for the minimum cycle cover problem
• Covering a graph with cuts of minimum total size
• A polynomial-time algorithm for max-min partitioning of ladders
• A simulated annealing approach to police district design
• Edge clique covers in graphs with independence number two
• Approximation and parameterized algorithms for balanced connected partition problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Biclique covers and partitions
• New models for commercial territory design
• Graph clustering
• On the kernel size of clique cover reductions for random intersection graphs
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Factors and factorizations of graphs. Proof techniques in factor theory
• A branch and bound algorithm for the capacitated vehicle routing problem
• Size-constrained graph partitioning polytopes
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Min-max tree covers of graphs.
• Facets of the clique partitioning polytope
• Applications of edge coverings by cliques
• Approximation results for a min-max location-routing problem
• Shortest coverings of graphs with cycles
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• A simple lower bound on edge coverings by cliques
• Path decomposition of graphs with given path length
• Graph factors and factorization: 1985--2003: a survey
• On the relationship between ATSP and the cycle cover problem
• Three ways to cover a graph
• Clique partitions of complements of forests and bounded degree graphs
• A reactive GRASP for a commercial territory design problem with multiple balancing requirements
• Approximation hardness of min-max tree covers
• On the decomposition of graphs into complete bipartite graphs
• Algorithms for compact letter displays: comparison and evaluation
• On covering graphs by complete bipartite subgraphs
• On the complexity of partitioning graphs into connected subgraphs
• An Erdős-Gallai conjecture
• Cycle covering in bridgeless graphs
• Covering graphs by the minimum number of equivalence relations
• Solving a large scale districting problem: A case report
• A cutting plane algorithm for a clustering problem
• Clique partitions and clique coverings
• Biclique decompositions and Hermitian rank
• Bipartite dimensions and bipartite degrees of graphs
• On the coverings of graphs
• On a clique covering problem of Orlin
• Asymptotic values of clique partition numbers
• On the complexity of finding multi-constrained spanning trees
• On clique partitions of split graphs
• The vehicle routing problem: An overview of exact and approximate algorithms
• Covering the edge set of a directed graph with trees
• On partitions of graphs into trees
• Cliques and clustering: A combinatorial approach
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• The node capacitated graph partitioning problem: A computational study
• Min-cut clustering
• A survey of constrained classification
• Covering a graph by complete bipartite graphs
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• Cluster analysis and mathematical programming
• A branch-and-cut algorithm for the equicut problem
• Clustering on trees
• Graph partitioning using linear and semidefinite programming
• Clique covering the edges of a locally cobipartite graph
• Proofs of two minimum circuit cover conjectures
• Exact approaches for solving a covering problem with capacitated subtrees
• Min-max cover of a graph with a small number of parts
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Maximum split clustering under connectivity constraints
• Path decompositions and Gallai's conjecture
• \(b\)-tree facets for the simple graph partitioning polytope
• Most uniform path partitioning and its use in image processing
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Extremal clique coverings of complementary graphs
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• An extension of Christofides heuristic to the k-person travelling salesman problem
• Subgraph coverings and edge switchings
• A tabu search heuristic and adaptive memory procedure for political districting
• Facets of the \(k\)-partition polytope
• Some new classes of facets for the equicut polytope
• Covering the edges of a connected graph by paths
• On edge perfectness and classes of bipartite graphs
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• Fast constructive and improvement heuristics for edge clique covering
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Minimum cycle partition with length requirements
• Regarding two conjectures on clique and biclique partitions
• Cut and flow formulations for the balanced connected \(k\)-partition problem
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• A dual bounding scheme for a territory design problem
• New LP relaxations for minimum cycle/path/tree cover problems
• The partition problem
• Chromatic characterization of biclique covers
• Efficiently covering complex networks with cliques of similar vertices
• Determining optimal police patrol areas with maximal covering and backup covering location models
• Weighted Voronoi region algorithms for political districting
• Political districting: from classical models to recent approaches
• On path decompositions of \(2 k\)-regular graphs
• Better approximability results for min-max tree/cycle/path cover problems
• Partitioning a weighted tree into subtrees with weights in a given range
• Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
• Facet-defining inequalities for the simple graph partitioning polytope
• On biclique coverings
• Local search algorithms for political districting