Minimum degree orderings

DOI10.1007/S00453-008-9239-2zbMATH Open1187.68352OpenAlexW2170044697MaRDI QIDQ848936FDOQ848936

Authors: Hiroshi Nagamochi 

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9239-2

Recommendations

• Minimum Degree Orderings
• On minimizing symmetric set functions
• Minimizing symmetric submodular functions
• Minimal orderings revisited
• Computing minimum cuts in hypergraphs

zbMATH Keywords

graph algorithmsedge-connectivitysubmodular functionsminimum cutsextreme subsetsmaximum adjacency orderingsminimum degree orderingsposi-modular functions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Cites Work

• Smallest-last ordering and clustering and graph coloring algorithms
• Minimizing symmetric submodular functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A note on minimizing submodular functions
• Multi-Terminal Network Flows
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• k-Components, Clusters and Slicings in Graphs
• A new approach to the minimum cut problem
• Minimum Cost Source Location Problems with Flow Requirements
• A simple min-cut algorithm
• Minimum cuts in near-linear time
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Title not available (Why is that?)
• Edge-connectivity augmentation problems
• A correctness certificate for the Stoer-Wagner min-cut algorithm
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• Cutsets and partitions of hypergraphs
• Minimum cost subpartitions in graphs

Cited In (7)

• Parsimonious formulations for low-diameter clusters
• On minimizing symmetric set functions
• Maximizing symmetric submodular functions
• Minimum Degree Orderings
• Some results about the contractions and the pendant pairs of a submodular system
• Posimodular function optimization
• Why is maximum clique often easy in practice?

This page was built for publication: Minimum degree orderings

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