Graph-Theoretic Concepts in Computer Science

DOI10.1007/b104584zbMath1112.68420MaRDI QIDQ5710806

Dieter Kratsch, Fedor V. Fomin, Gerhard J. Woeginger

Publication date: 8 December 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b104584

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Unnamed Item, Unnamed Item, Fine-Grained Reductions and Quantum Speedups for Dynamic Programming., On the Complexity of Bounded Context Switching., Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets, Finding large degree-anonymous subgraphs is hard, Parameterized complexity of conflict-free set cover, Fine-grained complexity of safety verification, Parameterized Complexity of Graph Burning, Assigning channels via the meet-in-the-middle approach, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Exact algorithms for dominating set, Lower bounds on kernelization, Exact exponential algorithms to find tropical connected sets of minimum size, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, Dynamic parameterized problems, The complexity ecology of parameters: An illustration using bounded max leaf number, Solving connected dominating set faster than \(2^n\), Finding a dominating set on bipartite graphs, Efficiency in exponential time for domination-type problems, On two techniques of combining branching and treewidth, Vertex and edge covers with clustering properties: Complexity and algorithms, A randomized algorithm for determining dominating sets in graphs of maximum degree five, Pathwidth of cubic graphs and exact algorithms, Exact algorithms for edge domination, Refined parameterizations for computing colored cuts in edge-colored graphs, Parameterized complexity of graph burning, Analyzing the reachability problem in choice networks, Inclusion/exclusion meets measure and conquer, The graph motif problem parameterized by the structure of the input graph, Solving Capacitated Dominating Set by using covering by subsets and maximum matching, An exact algorithm for the minimum dominating clique problem, A Faster Algorithm for Dominating Set Analyzed by the Potential Method, Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size, Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching