Revising Johnson's table for the 21st century (Q2091799): Difference between revisions

@@ Property / cites work @@
+Q3888545
@@ Property / cites work: Q3888545 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
+Normal rank
@@ Property / cites work @@
+Complexity of Finding Embeddings in a <i>k</i>-Tree
+Normal rank
@@ Property / cites work @@
+Linear time algorithms for NP-hard problems restricted to partial k- trees
+Normal rank
@@ Property / cites work @@
+The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Graph classes with structured neighborhoods and algorithmic applications
+Normal rank
@@ Property / cites work @@
+Generalized planar matching
@@ Property / cites work: Generalized planar matching / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian circuits in interval graph generalizations
+Normal rank
@@ Property / cites work @@
+Fourier meets M\"{o}bius: fast subset convolution
@@ Property / cites work: Fourier meets M\"{o}bius: fast subset convolution / rank @@
+Normal rank
@@ Property / cites work @@
+Clique Cover on Sparse Networks
@@ Property / cites work: Clique Cover on Sparse Networks / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Q4942616
@@ Property / cites work: Q4942616 / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Complexity of Independent Set in H-Free Graphs.
+Normal rank
@@ Property / cites work @@
+Dominating Sets in Chordal Graphs
@@ Property / cites work: Dominating Sets in Chordal Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized domination in circle graphs
@@ Property / cites work: Parameterized domination in circle graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Rooted directed path graphs are leaf powers
@@ Property / cites work: Rooted directed path graphs are leaf powers / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
+Normal rank
@@ Property / cites work @@
+Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
+Normal rank
@@ Property / cites work @@
+NP-completeness of edge-colouring some restricted graphs
+Normal rank
@@ Property / cites work @@
+Partition into cliques for cubic graphs: Planar case, complexity and approximation
+Normal rank
@@ Property / cites work @@
+Genus characterizes the complexity of certain graph problems: Some tight results
+Normal rank
@@ Property / cites work @@
+Improved Parameterized Upper Bounds for Vertex Cover
+Normal rank
@@ Property / cites work @@
+Unit disk graphs
@@ Property / cites work: Unit disk graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3684150
@@ Property / cites work: Q3684150 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time solvable optimization problems on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Upper bounds to the clique width of graphs
@@ Property / cites work: Upper bounds to the clique width of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating set is fixed parameter tractable in claw-free graphs
+Normal rank
@@ Property / cites work @@
+The Hamiltonian circuit problem for circle graphs is NP-complete
+Normal rank
@@ Property / cites work @@
+Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
+Normal rank
@@ Property / cites work @@
+Q4425961
@@ Property / cites work: Q4425961 / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
+Normal rank
@@ Property / cites work @@
+Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
+Normal rank
@@ Property / cites work @@
+Q5272625
@@ Property / cites work: Q5272625 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4850549
@@ Property / cites work: Q4850549 / rank @@
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / rank @@
+Normal rank
@@ Property / cites work @@
+The steiner problem in graphs
@@ Property / cites work: The steiner problem in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The dominating set problem is fixed parameter tractable for graphs of bounded genus
+Normal rank
@@ Property / cites work @@
+Kernelization
@@ Property / cites work: Kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Coloring Circular Arcs and Chords
+Normal rank
@@ Property / cites work @@
+Some simplified NP-complete graph problems
@@ Property / cites work: Some simplified NP-complete graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+A recognition algorithm for the intersection graphs of paths in trees
+Normal rank
@@ Property / cites work @@
+Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
+Normal rank
@@ Property / cites work @@
+The behavior of clique-width under graph operations and graph transformations
+Normal rank
@@ Property / cites work @@
+Maximum cut on line and total graphs
@@ Property / cites work: Maximum cut on line and total graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4368728
@@ Property / cites work: Q4368728 / rank @@
+Normal rank
@@ Property / cites work @@
+Domination When the Stars Are Out
@@ Property / cites work: Domination When the Stars Are Out / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Branch-Decompositions and Rank-Decompositions
+Normal rank
@@ Property / cites work @@
+The NP-Completeness of Edge-Coloring
@@ Property / cites work: The NP-Completeness of Edge-Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Hamilton Paths in Grid Graphs
@@ Property / cites work: Hamilton Paths in Grid Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Mim-width. III. Graph powers and generalized distance domination problems
+Normal rank
@@ Property / cites work @@
+The NP-completeness column: an ongoing guide
@@ Property / cites work: The NP-completeness column: an ongoing guide / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Recent developments on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of domination problems in circle graphs
+Normal rank
@@ Property / cites work @@
+Approximating the minimum clique cover and other hard problems in subtree filament graphs
+Normal rank
@@ Property / cites work @@
+Q2766822
@@ Property / cites work: Q2766822 / rank @@
+Normal rank
@@ Property / cites work @@
+Edge dominating set and colorings on graphs with fixed clique-width
+Normal rank
@@ Property / cites work @@
+Q4448764
@@ Property / cites work: Q4448764 / rank @@
+Normal rank
@@ Property / cites work @@
+Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
+Normal rank
@@ Property / cites work @@
+On the Algorithmic Complexity of Total Domination
@@ Property / cites work: On the Algorithmic Complexity of Total Domination / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
+Normal rank
@@ Property / cites work @@
+Hardness of r-dominating set on Graphs of Diameter (r + 1)
+Normal rank
@@ Property / cites work @@
+A Linear Time Algorithm for Deciding Interval Graph Isomorphism
+Normal rank
@@ Property / cites work @@
+On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
+Normal rank
@@ Property / cites work @@
+Parameterizing above Guaranteed Values: MaxSat and MaxCut
+Normal rank
@@ Property / cites work @@
+Genus g Graphs Have Pagenumber O(√g)
@@ Property / cites work: Genus g Graphs Have Pagenumber O(√g) / rank @@
+Normal rank
@@ Property / cites work @@
+Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
+Normal rank
@@ Property / cites work @@
+Q3740256
@@ Property / cites work: Q3740256 / rank @@
+Normal rank
@@ Property / cites work @@
+Bandwidth contrained NP-complete problems
@@ Property / cites work: Bandwidth contrained NP-complete problems / rank @@
+Normal rank
@@ Property / cites work @@
+Intersection graphs of paths in a tree
@@ Property / cites work: Intersection graphs of paths in a tree / rank @@
+Normal rank
@@ Property / cites work @@
+HAMILTONian circuits in chordal bipartite graphs
@@ Property / cites work: HAMILTONian circuits in chordal bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
+Normal rank
@@ Property / cites work @@
+Bounded clique cover of some sparse graphs
@@ Property / cites work: Bounded clique cover of some sparse graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating rank-width and clique-width quickly
@@ Property / cites work: Approximating rank-width and clique-width quickly / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating clique-width and branch-width
@@ Property / cites work: Approximating clique-width and branch-width / rank @@
+Normal rank
@@ Property / cites work @@
+Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
+Normal rank
@@ Property / cites work @@
+Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
+Normal rank
@@ Property / cites work @@
+The complexity of SIMPLE MAX-CUT on comparability graphs
+Normal rank
@@ Property / cites work @@
+Q4770411
@@ Property / cites work: Q4770411 / rank @@
+Normal rank
@@ Property / cites work @@
+Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
+Normal rank
@@ Property / cites work @@
+MSOL partitioning problems on graphs of bounded treewidth and clique-width
+Normal rank
@@ Property / cites work @@
+An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
+Normal rank
@@ Property / cites work @@
+Efficient graph representations
@@ Property / cites work: Efficient graph representations / rank @@
+Normal rank
@@ Property / cites work @@
+Q3343454
@@ Property / cites work: Q3343454 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
+Normal rank
@@ Property / cites work @@
+Q3787505
@@ Property / cites work: Q3787505 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3663321
@@ Property / cites work: Q3663321 / rank @@
+Normal rank
@@ Property / cites work @@
+Steiner trees, partial 2–trees, and minimum IFI networks
+Normal rank
@@ Property / cites work @@
+\(k\)-NLC graphs and polynomial algorithms
@@ Property / cites work: \(k\)-NLC graphs and polynomial algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Steiner trees, connected domination and strongly chordal graphs
+Normal rank
@@ Property / cites work @@
+Steiner problem in Halin networks
@@ Property / cites work: Steiner problem in Halin networks / rank @@
+Normal rank
@@ Property / cites work @@
+Node-and edge-deletion NP-complete problems
@@ Property / cites work: Node-and edge-deletion NP-complete problems / rank @@
+Normal rank