3-coloring in time

DOI10.1016/j.jalgor.2004.06.008zbMath1101.68716OpenAlexW1533811829WikidataQ56269083 ScholiaQ56269083MaRDI QIDQ4652410

Richard Beigel, David Eppstein

Publication date: 22 February 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.06.008

zbMATH Keywords

Girsanov theoremWasserstein distanceLoop groupsConstraint Satisfaction\(H\)-distanceHeat measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (38)

An approximate algorithm for the chromatic number of graphs ⋮ Improved edge-coloring with three colors ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Word-Representable Graphs: a Survey ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Exact algorithms for maximum induced matching ⋮ Complement, Complexity, and Symmetric Representation ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Dominating set based exact algorithms for \(3\)-coloring ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ Three colorability characterized by shrinking of locally connected subgraphs into triangles ⋮ Decomposition of realizable fuzzy relations ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ Determining the \(L(2,1)\)-span in polynomial space ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Regular inference as vertex coloring ⋮ Unnamed Item ⋮ ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS ⋮ On the representation number of a crown graph ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7 ⋮ Alternative representations of P systems solutions to the graph colouring problem ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Deconstructing Intractability: A Case Study for Interval Constrained Coloring ⋮ A note on coloring sparse random graphs ⋮ Improved simulation of nondeterministic Turing machines ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Word-representability of Toeplitz graphs ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

This page was built for publication: 3-coloring in time