On Computational Aspects of Greedy Partitioning of Graphs

DOI10.1007/978-3-319-59605-1_4MaRDI QIDQ4632201zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 4170931 (Why is no real title available?)
• scientific article; zbMATH DE number 3800939 (Why is no real title available?)
• A lower bound for approximating the Grundy number
• A note on first-fit coloring of interval graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• An interpolation theorem for partitions which are complete with respect to hereditary properties
• Dynamic coloring of graphs
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• New bounds for the chromatic number of graphs
• New potential functions for greedy independence and coloring
• On the Grundy number of graphs with few P₄'s
• On-line 3-chromatic graphs. II: Critical graphs
• Results on the Grundy chromatic number of graphs
• Some perfect coloring properties of graphs
• Some simplified NP-complete graph problems
• The complexity of generalized graph colorings

Cited in

(8)

• scientific article; zbMATH DE number 910878 (Why is no real title available?)
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 4094840 (Why is no real title available?)
• Computational aspects of greedy partitioning of graphs
• scientific article; zbMATH DE number 3983202 (Why is no real title available?)
• Partitioning graphs on message-passing machines by pairwise mincut
• On generalized greedy splitting algorithms for multiway partition problems
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

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)