Graph Classes with Structured Neighborhoods and Algorithmic Applications

DOI10.1007/978-3-642-25870-1_6zbMath1341.05218MaRDI 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 algorithms; vertex partitioning problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C22: Signed and weighted graphs

Related Items

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

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