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