{"id":"W3027090837","doi":"10.1007/s00453-020-00716-4","title":"The Inverse Voronoi Problem in Graphs I: Hardness","year":2020,"lang":"en","type":"article","venue":"Algorithmica","topic":"Computational Geometry and Mesh Generation","field":"Computer Science","cited_by":4,"is_retracted":false,"has_abstract":false,"ca_institutions":"Simon Fraser University","funders":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada; Ministerio de Asuntos Económicos y Transformación Digital, Gobierno de España; Javna Agencija za Raziskovalno Dejavnost RS; Agence Nationale de la Recherche","keywords":"Voronoi diagram; Parameterized complexity; Combinatorics; Mathematics; Pathwidth; Treewidth; Discrete mathematics; Shortest path problem; Planar graph; Chordal graph; Graph; Geometry; Line graph","routes":{"ca_aff":true,"ca_fund":true,"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.001469865,0.001049482,0.002215096,0.001377481,0.002025275,0.005795381,0.003827817,0.003201683,0.01286453],"category_scores_gemma":[0.0157885,0.001195648,0.001943401,0.002523891,0.004826931,0.01276557,0.004140292,0.008598593,0.001816297],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002151814,"about_ca_system_score_gemma":0.001624034,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001917608,"about_ca_topic_score_gemma":0.001370461,"domain_scores_codex":[0.997929,0.0005553508,0.00007409417,0.0006022839,0.0006028402,0.0002364686],"domain_scores_gemma":[0.9891028,0.008941591,0.0004370831,0.0008598974,0.0003557951,0.0003026997],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0002743439,0.0001729995,0.00148332,0.0011358,0.00009507311,0.0001865926,0.0006601466,0.04523562,0.001382813,0.8424363,0.0421179,0.06481914],"study_design_scores_gemma":[0.00003734228,0.00002222407,0.0003411735,0.0000554142,0.00001867653,0.0001612308,0.000133902,0.0254631,0.0004447124,0.9648266,0.00848233,0.00001331171],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1004953,0.01494595,0.677931,0.02436815,0.001256426,0.000258598,0.002485826,0.001091087,0.1771677],"genre_scores_gemma":[0.8117147,0.01164261,0.1257541,0.003276038,0.003481343,0.000563448,0.00315695,0.0009168536,0.03949394],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01286453,"threshold_uncertainty_score":0.04303616,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0159190884315145,"score_gpt":0.2214472438777045,"score_spread":0.20552815544619,"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."}}