Minimum degree orderings

DOI10.1007/S00453-008-9239-2MaRDI QIDQ848936zbMATH OpenOpenAlexFDO

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

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)

Recommendations

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

Cites work

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

Cited in

(6)

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

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)