Computing the chromatic number using graph decompositions via matrix rank
From MaRDI portal
Publication:2330132
Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)
Recommendations
- Coloring graphs having few colorings over path decompositions
- Finer tight bounds for coloring on clique-width
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Finer tight bounds for coloring on clique-width
- Fine-grained parameterized complexity analysis of graph coloring problems
Cites work
- A note on graph colorings and graph polynomials
- A partial k-arboretum of graphs with bounded treewidth
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Between treewidth and clique-width
- Bounding the Independence Number of a Graph
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Coloring graphs having few colorings over path decompositions
- Colorings and orientations of graphs
- Competitive algorithms for generalized k-server in uniform metrics
- Cutwidth I: A linear time fixed parameter algorithm
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Cutwidth: obstructions and algorithmic aspects
- Data reduction for graph coloring problems
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Edge dominating set and colorings on graphs with fixed clique-width
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Fine-grained parameterized complexity analysis of graph coloring problems
- gCol
- Gröbner bases and graph colorings
- Guide to graph colouring. Algorithms and applications
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- scientific article; zbMATH DE number 1302184 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- Intractability of clique-width parameterizations
- Known algorithms on graphs of bounded treewidth are probably optimal
- Matching is as easy as matrix inversion
- On the complexity of k-SAT
- Parameterized algorithms
- Parameterized Algorithms for Modular-Width
- Searching and pebbling
- Set partitioning via inclusion-exclusion
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Some simplified NP-complete graph problems
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- The vertex separation and search number of a graph
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Tree-width, path-width, and cutwidth
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Which problems have strongly exponential complexity?
Cited in
(13)- Rank, term rank, and chromatic number
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Competitive Algorithms for Generalized k -Server in Uniform Metrics
- Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
- A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
- Exact and parameterized algorithms for choosability
- Towards exact structural thresholds for parameterized complexity
- Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
- Tight bounds for some classical problems parameterized by cutwidth
- Tight bounds for connected odd cycle transversal parameterized by clique-width
This page was built for publication: Computing the chromatic number using graph decompositions via matrix rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330132)
