Graph Classes with Structured Neighborhoods and Algorithmic Applications

DOI10.1007/978-3-642-25870-1_6zbMath1341.05218OpenAlexW1890176618MaRDI QIDQ3104764

Rémy Belmonte, Martin Vatshelle

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_6

zbMATH Keywords

polynomial time algorithmsvertex partitioning problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (5)

Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ Boolean-width of graphs ⋮ Sitting closer to friends than enemies, revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Independence and domination in polygon graphs
• Computing role assignments of chordal graphs
• Domination in convex and chordal bipartite graphs
• The rank-width of the square grid
• Clustering and domination in perfect graphs
• Graph minors. X: Obstructions to tree-decomposition
• Linear time algorithms on circular-arc graphs
• The complexity of domination problems in circle graphs
• Dominations in trapezoid graphs
• Linear-time recognition of circular-arc graphs
• Branch-width and well-quasi-ordering in matroids and graphs.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Fast algorithms for the dominating set problem on permutation graphs
• Approximating clique-width and branch-width
• On the Boolean-Width of a Graph: Structure and Applications
• Boolean-Width of Graphs
• Domination in permutation graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph

This page was built for publication: Graph Classes with Structured Neighborhoods and Algorithmic Applications