On Computational Aspects of Greedy Partitioning of Graphs

DOI10.1007/978-3-319-59605-1_4zbMATH Open1489.68183OpenAlexW2619471257WikidataQ62043601 ScholiaQ62043601MaRDI QIDQ4632201FDOQ4632201

Authors: Piotr Borowiecki 

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: http://link.springer.com/10.1007/s10878-017-0185-2

Recommendations

• Computational aspects of greedy partitioning of graphs
• scientific article; zbMATH DE number 3983202
• Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
• On the Grundy number of a graph
• scientific article; zbMATH DE number 2159638

zbMATH Keywords

computational complexitygreedy algorithmgraph coloringgraph partitioningGrundy numberminimal graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Some perfect coloring properties of graphs
• Some simplified NP-complete graph problems
• On-line 3-chromatic graphs. II: Critical graphs
• Results on the Grundy chromatic number of graphs
• New potential functions for greedy independence and coloring
• A lower bound for approximating the Grundy number
• The complexity of generalized graph colorings
• New bounds for the chromatic number of graphs
• Dynamic coloring of graphs
• Title not available (Why is that?)
• A note on first-fit coloring of interval graphs
• Title not available (Why is that?)
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• On the Grundy number of graphs with few \(P_4\)'s
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• An interpolation theorem for partitions which are complete with respect to hereditary properties

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational aspects of greedy partitioning of graphs
• Title not available (Why is that?)
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Partitioning graphs on message-passing machines by pairwise mincut
• On generalized greedy splitting algorithms for multiway partition problems

This page was built for publication: On Computational Aspects of Greedy Partitioning of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632201)