Revising Johnson's table for the 21st century
type: Item
instance of: scholarly article
title: Revising Johnson's table for the 21st century
zbMATH Open document ID: 1502.05184
author: Yanyan Li
published in: Discrete Applied Mathematics
publication date: 2022-11-02T00:00:00Z
full work available at URL: https://arxiv.org/abs/2104.14395
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7610741
zbMATH Keywords: computational complexity
zbMATH Keywords: parameterized complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: Steiner tree
zbMATH Keywords: dominating set
MaRDI profile type: Publication
OpenAlex ID: W3171927283
arXiv ID: 2104.14395
cites work: Q3888545
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Graph classes with structured neighborhoods and algorithmic applications
cites work: Generalized planar matching
cites work: Hamiltonian circuits in interval graph generalizations
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Clique Cover on Sparse Networks
cites work: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Q4942616
cites work: Parameterized Complexity of Independent Set in H-Free Graphs.
cites work: Dominating Sets in Chordal Graphs
cites work: Parameterized domination in circle graphs
cites work: Rooted directed path graphs are leaf powers
cites work: Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
cites work: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
cites work: NP-completeness of edge-colouring some restricted graphs
cites work: Partition into cliques for cubic graphs: Planar case, complexity and approximation
cites work: Genus characterizes the complexity of certain graph problems: Some tight results
cites work: Improved Parameterized Upper Bounds for Vertex Cover
cites work: Unit disk graphs
cites work: Q3684150
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Parameterized Algorithms
cites work: Dominating set is fixed parameter tractable in claw-free graphs
cites work: The Hamiltonian circuit problem for circle graphs is NP-complete
cites work: Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
cites work: Q4425961
cites work: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
cites work: Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
cites work: Q5272625
cites work: Q4850549
cites work: Fundamentals of parameterized complexity
cites work: The steiner problem in graphs
cites work: The dominating set problem is fixed parameter tractable for graphs of bounded genus
cites work: Kernelization
cites work: Q4198056
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Some simplified NP-complete graph problems
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: The behavior of clique-width under graph operations and graph transformations
cites work: Maximum cut on line and total graphs
cites work: Q4368728
cites work: Domination When the Stars Are Out
cites work: Finding Branch-Decompositions and Rank-Decompositions
cites work: The NP-Completeness of Edge-Coloring
cites work: Hamilton Paths in Grid Graphs
cites work: Mim-width. III. Graph powers and generalized distance domination problems
cites work: The NP-completeness column: an ongoing guide
cites work: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
cites work: Recent developments on graphs of bounded clique-width
cites work: Reducibility among Combinatorial Problems
cites work: The complexity of domination problems in circle graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Approximating the minimum clique cover and other hard problems in subtree filament graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Q2766822

Revising Johnson's table for the 21st century (cites work)
cites work: Edge dominating set and colorings on graphs with fixed clique-width

Revising Johnson's table for the 21st century (cites work)
cites work: Q4448764

Revising Johnson's table for the 21st century (cites work)
cites work: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

Revising Johnson's table for the 21st century (cites work)
cites work: On the Algorithmic Complexity of Total Domination

Revising Johnson's table for the 21st century (cites work)
cites work: A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Hardness of r-dominating set on Graphs of Diameter (r + 1)

Revising Johnson's table for the 21st century (cites work)
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism

Revising Johnson's table for the 21st century (cites work)
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut

Revising Johnson's table for the 21st century (cites work)
cites work: Genus g Graphs Have Pagenumber O(√g)

Revising Johnson's table for the 21st century (cites work)
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover

Revising Johnson's table for the 21st century (cites work)
cites work: Q3740256

Revising Johnson's table for the 21st century (cites work)
cites work: Bandwidth contrained NP-complete problems

Revising Johnson's table for the 21st century (cites work)
cites work: Intersection graphs of paths in a tree

Revising Johnson's table for the 21st century (cites work)
cites work: HAMILTONian circuits in chordal bipartite graphs

Revising Johnson's table for the 21st century (cites work)
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Bounded clique cover of some sparse graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Q5710169

Revising Johnson's table for the 21st century (cites work)
cites work: Approximating rank-width and clique-width quickly

Revising Johnson's table for the 21st century (cites work)
cites work: Approximating clique-width and branch-width

Revising Johnson's table for the 21st century (cites work)
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

Revising Johnson's table for the 21st century (cites work)
cites work: Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

Revising Johnson's table for the 21st century (cites work)
cites work: The complexity of SIMPLE MAX-CUT on comparability graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Q4770411

Revising Johnson's table for the 21st century (cites work)
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

Revising Johnson's table for the 21st century (cites work)
cites work: MSOL partitioning problems on graphs of bounded treewidth and clique-width

Revising Johnson's table for the 21st century (cites work)
cites work: An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Efficient graph representations

Revising Johnson's table for the 21st century (cites work)
cites work: Q3343454

Revising Johnson's table for the 21st century (cites work)
cites work: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Q3787505

Revising Johnson's table for the 21st century (cites work)
cites work: Q3663321

Revising Johnson's table for the 21st century (cites work)
cites work: Steiner trees, partial 2–trees, and minimum IFI networks

Revising Johnson's table for the 21st century (cites work)
cites work: \(k\)-NLC graphs and polynomial algorithms

Revising Johnson's table for the 21st century (cites work)
cites work: Steiner trees, connected domination and strongly chordal graphs

Revising Johnson's table for the 21st century (cites work)
cites work: Steiner problem in Halin networks

Revising Johnson's table for the 21st century (cites work)
cites work: Node-and edge-deletion NP-complete problems

Revising Johnson's table for the 21st century (DOI)
DOI: 10.1016/J.DAM.2021.05.021