Smallest-last ordering and clustering and graph coloring algorithms
From MaRDI portal
Publication:3765255
DOI10.1145/2402.322385zbMATH Open0628.68054DBLPjournals/jacm/MatulaB83OpenAlexW2094224753WikidataQ57259028 ScholiaQ57259028MaRDI QIDQ3765255FDOQ3765255
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (72)
- Targeted \(k\)-node collapse problem: towards understanding the robustness of local \(k\)-core structure
- Cost Minimisation in Multi-interface Networks
- Bisectored unit disk graphs
- Title not available (Why is that?)
- Efficient deterministic algorithms for embedding graphs on books
- Sublinear time estimation of degree distribution moments: the arboricity connection
- Parameterized leaf power recognition via embedding into graph products
- Bounds and algorithms for graph trusses
- Proof-labeling schemes: broadcast, unicast and in between
- Going far from degeneracy
- On Fault-Tolerant Low-Diameter Clusters in Graphs
- Approximation algorithms for minimum latency data aggregation in wireless sensor networks with directional antenna
- Relaxed approximate coloring in exact maximum clique search
- Approximation algorithms for the weighted independent set problem in sparse graphs
- 2-coloring number revisited
- Parsimonious formulations for low-diameter clusters
- Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
- Location-oblivious distributed unit disk graph coloring
- On two coloring problems in mixed graphs
- Finding and counting given length cycles
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Minimum degree orderings
- Lower bounds for on-line graph coloring
- Counting Homomorphic Cycles in Degenerate Graphs
- OVSF-CDMA code assignment in wireless ad hoc networks
- A constructive arboricity approximation scheme
- Computing inductive vertex orderings
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- Graph signatures: identification and optimization
- Cluster analysis and mathematical programming
- Minimum k‐cores and the k‐core polytope
- Mathematical programming formulations for the collapsed k-core problem
- In search of the densest subgraph
- Title not available (Why is that?)
- Approximation for a scheduling problem with application in wireless networks
- Independent sets in graphs
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Knowledge cores in large formal contexts
- Equitable list tree-coloring of bounded treewidth graphs
- Designing optimally multiplexed SNP genotyping assays
- A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
- Locally defined independence systems on graphs
- Maximum scan statistics and channel assignment problems in homogeneous wireless networks
- A sequential coloring algorithm for finite sets
- Sum coloring and interval graphs: A tight upper bound for the minimum number of colors
- Computing the depth distribution of a set of boxes
- 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 note on direct methods for approximations of sparse Hessian matrices
- Exploring the kernelization borders for hitting cycles
- Efficient enumeration of dominating sets for sparse graphs
- Efficient enumeration of dominating sets for sparse graphs
- Graph kernels: a survey
- Consecutive colorings of graphs
- Density decompositions of networks
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- Parameterized leaf power recognition via embedding into graph products
- Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy
- Scaling-up reasoning and advanced analytics on BigData
- The smallest hard-to-color graph for the SL algorithm
- Title not available (Why is that?)
- Counting Subgraphs in Degenerate Graphs
- Why is maximum clique often easy in practice?
- Efficiently enumerating all maximal cliques with bit-parallelism
- Worst-case analysis of clique MIPs
- Software for estimating sparse Jacobian matrices
- Estimation of sparse hessian matrices and graph coloring problems
- Exact algorithms for maximum clique: a computational study
- \((p,k)\)-coloring problems in line graphs
- Cost minimization in wireless networks with a bounded and unbounded number of interfaces
- A constant factor approximation algorithm for the storage allocation problem
This page was built for publication: Smallest-last ordering and clustering and graph coloring algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3765255)
