{"id":"W3115154750","doi":"10.48550/arxiv.1907.12119","title":"A Fast Minimum Degree Algorithm and Matching Lower Bound","year":2019,"lang":"en","type":"article","venue":"arXiv (Cornell University)","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"Degree (music); Heuristics; Time complexity; Combinatorics; Algorithm; Mathematics; Running time; Binary logarithm; Reduction (mathematics); Graph; Simple (philosophy); Upper and lower bounds; Combinatorial algorithms; Discrete mathematics; Computer science; Mathematical optimization","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002137069,0.001779063,0.00152572,0.002065237,0.001901843,0.003850848,0.003740792,0.002478354,0.01638319],"category_scores_gemma":[0.01546451,0.0009467013,0.002081194,0.003299664,0.001631653,0.009154558,0.004483944,0.003942035,0.006087075],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003146401,"about_ca_system_score_gemma":0.003514697,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003047363,"about_ca_topic_score_gemma":0.004423785,"domain_scores_codex":[0.9946209,0.0009025281,0.0002387091,0.001533049,0.001745776,0.0009590036],"domain_scores_gemma":[0.9929703,0.003712481,0.0004420844,0.001711849,0.000811877,0.0003513844],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0007193767,0.0005696228,0.001840537,0.0006726932,0.0001261625,0.0002266635,0.0002914272,0.1987375,0.01502757,0.4339424,0.03782961,0.3100165],"study_design_scores_gemma":[0.0001381762,0.0001778138,0.0004282234,0.00007759794,0.00006045996,0.0003079289,0.00006823176,0.601866,0.007459465,0.3706207,0.01873736,0.0000579023],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.01971241,0.0008721374,0.9466928,0.00204802,0.0002174041,0.0002281208,0.00058476,0.002659707,0.02698459],"genre_scores_gemma":[0.2421262,0.001031743,0.7310718,0.001369531,0.0004053163,0.0004673607,0.001899256,0.001289344,0.02033947],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.01638319,"threshold_uncertainty_score":0.05480725,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.047551259976895,"score_gpt":0.2032968253776011,"score_spread":0.1557455654007061,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}