Smallest-last ordering and clustering and graph coloring algorithms
From MaRDI portal
Publication:3765255
DOI10.1145/2402.322385zbMath0628.68054OpenAlexW2094224753WikidataQ57259028 ScholiaQ57259028MaRDI QIDQ3765255
Leland L. Beck, David W. Matula
Publication date: 1983
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2402.322385
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Lower bounds for on-line graph coloring, Counting Subgraphs in Degenerate Graphs, Minimum degree orderings, On Fault-Tolerant Low-Diameter Clusters in Graphs, Knowledge cores in large formal contexts, A note on direct methods for approximations of sparse Hessian matrices, Efficiently enumerating all maximal cliques with bit-parallelism, Scaling-up reasoning and advanced analytics on BigData, Cluster analysis and mathematical programming, Approximation algorithms for minimum latency data aggregation in wireless sensor networks with directional antenna, Proof-labeling schemes: broadcast, unicast and in between, Counting Homomorphic Cycles in Degenerate Graphs, Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs, Minimum k‐cores and the k‐core polytope, Consecutive colorings of graphs, On two coloring problems in mixed graphs, Mathematical programming formulations for the collapsed k-core problem, Efficient deterministic algorithms for embedding graphs on books, Bounds and algorithms for graph trusses, Going Far from Degeneracy, Equitable list tree-coloring of bounded treewidth graphs, Parsimonious formulations for low-diameter clusters, Note on coloring of double disk graphs, Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs, A Constructive Arboricity Approximation Scheme, Unnamed Item, Why Is Maximum Clique Often Easy in Practice?, Exact algorithms for maximum clique: a computational study, Computing inductive vertex orderings, Parameterized Leaf Power Recognition via Embedding into Graph Products, Efficient enumeration of dominating sets for sparse graphs, Independent sets in graphs, Finding and counting given length cycles, Exploring the Kernelization Borders for Hitting Cycles, Graph signatures: identification and optimization, OVSF-CDMA code assignment in wireless ad hoc networks, A constant factor approximation algorithm for the storage allocation problem, Location-oblivious distributed unit disk graph coloring, Relaxed approximate coloring in exact maximum clique search, In search of the densest subgraph, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, Unnamed Item, Unnamed Item, Software for estimating sparse Jacobian matrices, Designing optimally multiplexed SNP genotyping assays, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Unnamed Item, Parameterized aspects of triangle enumeration, Approximation for a scheduling problem with application in wireless networks, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Cost Minimisation in Multi-interface Networks, Computing the depth distribution of a set of boxes, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, Maximum scan statistics and channel assignment problems in homogeneous wireless networks, The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices, Approximation algorithms for the weighted independent set problem in sparse graphs, Density decompositions of networks, Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy, Sum coloring and interval graphs: A tight upper bound for the minimum number of colors, Bisectored unit disk graphs, Parameterized leaf power recognition via embedding into graph products, A sequential coloring algorithm for finite sets, 2-coloring number revisited, Worst-case analysis of clique MIPs, Locally defined independence systems on graphs, Estimation of sparse hessian matrices and graph coloring problems, Graph Kernels: A Survey, Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees, \((p,k)\)-coloring problems in line graphs
