3-coloring in time
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
Recommendations
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Worst-case time bounds for coloring and satisfiability problems
- Dominating set based exact algorithms for 3-coloring
- Improved algorithms for counting solutions in constraint satisfaction problems
- Improved Edge-Coloring with Three Colors
Cited in
(49)- Efficient approximation of Min Set Cover by moderately exponential algorithms
- A note on coloring sparse random graphs
- Three colorability characterized by shrinking of locally connected subgraphs into triangles
- On the representation number of a crown graph
- Dominating set based exact algorithms for 3-coloring
- Decomposition of realizable fuzzy relations
- Enumerating the edge-colourings and total colourings of a regular graph
- Trimmed Moebius inversion and graphs of bounded degree
- Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
- Exact algorithms for counting 3-colorings of graphs
- Alternative representations of P systems solutions to the graph colouring problem
- Word-representability of Toeplitz graphs
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Exact algorithms for maximum induced matching
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Sharp separation and applications to exact and parameterized algorithms
- Determining the \(L(2,1)\)-span in polynomial space
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Improved worst-case complexity for the MIN 3-SET COVERING problem
- An approximate algorithm for the chromatic number of graphs
- Complement, complexity, and symmetric representation
- Colorings with few colors: counting, enumeration and combinatorial bounds
- A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)
- Deconstructing Intractability: A Case Study for Interval Constrained Coloring
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- Word-Representable Graphs: a Survey
- On 4-edge coloring of cubic graphs containing ``small non-planar subgraphs
- Regular inference as vertex coloring
- Worst-case time bounds for coloring and satisfiability problems
- A separator theorem for hypergraphs and a CSP-SAT algorithm
- Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
- Improved algorithms for counting solutions in constraint satisfaction problems
- Exponential-time quantum algorithms for graph coloring problems
- Deciding 3-colourability in less than O(1.415n) steps
- Branch and recharge: exact algorithms for generalized domination
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- A piecewise approach for the analysis of exact algorithms
- Faster algorithm for unique (k,2)-CSP
- A piecewise approach for the analysis of exact algorithms
- Fast exact algorithms for the SAT problem with bounded occurrences of variables
- Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
- On connections between k-coloring and Euclidean k-means
- Improved simulation of nondeterministic Turing machines
- Improved edge-coloring with three colors
- Solving connected dominating set faster than \(2^n\)
- Computing branchwidth via efficient triangulations and blocks
- Simple and improved parameterized algorithms for multiterminal cuts
This page was built for publication: 3-coloring in time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4652410)
