Publication:5503435
From MaRDI portal
zbMath1169.68653MaRDI QIDQ5503435
Pinar Heggernes, Dieter Kratsch
Publication date: 15 January 2009
Related Items
On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency, On the Complexity of Finding a Potential Community, Acyclic Matching in Some Subclasses of Graphs, Finding a chain graph in a bipartite permutation graph, Competitive Diffusion on Weighted Graphs, Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection, Ferrers dimension of grid intersection graphs, Betti numbers and anti-lecture Hall compositions of random threshold graphs, Cover-incomparability graphs and chordal graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, Solving Matching Problems Efficiently in Bipartite Graphs, Certifying induced subgraphs in large graphs, Acyclic matching in some subclasses of graphs, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, Computational aspects of double dominating sequences in graphs, Transitivity on subclasses of chordal graphs, Characterization and recognition of Radon-independent sets in split graphs, Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, The maximum cardinality cut problem in co-bipartite chain graphs, Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs, Edge contractions in subclasses of chordal graphs, Cosecure domination: hardness results and algorithms, Complexity of total dominator coloring in graphs, Computation of Grundy dominating sequences in (co-)bipartite graphs, A simple certifying algorithm for 3-edge-connectivity, Some new algorithmic results on co-secure domination in graphs, Algorithms and hardness results for edge total domination problem in graphs, Structural parameters for scheduling with assignment restrictions, Positional Dominance: Concepts and Algorithms, Approximating the path-distance-width for AT-free graphs and graphs in related classes, Subgraph isomorphism in graph classes, Certifying algorithms, Some new considerations about double nested graphs, Finding a potential community in networks, Edge Contractions in Subclasses of Chordal Graphs, Approximate association via dissociation, A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs, Strict chordal and strict split digraphs, \(1\)-perfectly orientable graphs and graph products, Recognition of split-graphic sequences, Edge deletion problems: branching facilitated by modular decomposition, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time, The complexity of the defensive domination problem in special graph classes, Letter graphs and geometric grid classes of permutations: characterization and recognition, On the complexity of minimum maximal uniquely restricted matching, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, On minimal forbidden subgraph characterizations of balanced graphs, Approximability of the Path-Distance-Width for AT-free Graphs, Role coloring bipartite graphs, Counting and enumerating independent sets with applications to combinatorial optimization problems, Algorithms for maximum internal spanning tree problem for some graph classes, Graph Classes and Forbidden Patterns on Three Vertices, Transitivity on subclasses of bipartite graphs, Fast Diameter Computation within Split Graphs
