Graph-Theoretic Concepts in Computer Science

DOI10.1007/b104584zbMath1112.68420MaRDI QIDQ5710806

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

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

Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets, Finding large degree-anonymous subgraphs is hard, 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, 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, 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