An overview of graph covering and partitioning

DOI10.1016/J.DISC.2022.112884MaRDI QIDQ2142633zbMATH OpenOpenAlexFDO

Authors 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

edge coveringgraph partitioningvertex covering

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3851110
• scientific article; zbMATH DE number 3908486
• scientific article; zbMATH DE number 1454641
• scientific article; zbMATH DE number 1236360
• Graph partitions: recent progresses and some open problems

Cites work

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

Cited in

(14)

• Political districting to minimize cut edges
• Partitions and well-coveredness: the graph sandwich problem
• scientific article; zbMATH DE number 3851110 (Why is no real title available?)
• scientific article; zbMATH DE number 3908486 (Why is no real title available?)
• An efficient heuristic for the \(k\)-partitioning problem
• Vertex covering with capacitated trees
• The heterogeneous rooted tree cover problem
• A fast 3-approximation for the capacitated tree cover problem with edge loads
• Injective colorings of Sierpiński-like graphs and Kneser graphs
• Approximating graphic min-max and minimum cycle/path/tree cover problems
• Approximation algorithms for solving the heterogeneous rooted tree/path cover problems
• Partitions of graphs into special bipartite graphs
• Compact representation of semilinear and terrain-like graphs
• Maximin share fair division of a k-uniform hypergraph

Describes a project that uses

Uses Software

• MESHPART
• VRP
• PERL
• MCODE

This page was built for publication: An overview of graph covering and partitioning

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