scientific article; zbMATH DE number 5492533
From MaRDI portal
Publication:5503435
zbMath1169.68653MaRDI QIDQ5503435
Pinar Heggernes, Dieter Kratsch
Publication date: 15 January 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (56)
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
This page was built for publication: