Čibej, U. and Li, A. and Miklós, István and Nasir, S. and Srikanth, V. (2023) Constructing bounded degree graphs with prescribed degree and neighbor degree sequences. DISCRETE APPLIED MATHEMATICS, 332. pp. 47-61. ISSN 0166-218X
|
Text
2109.12993v1.pdf Download (238kB) | Preview |
Abstract
Let D=(d1,d2,…,dn) and F=(f1,f2,…,fn) be two sequences of positive integers. We consider the following decision problems: is there a (i) multigraph, (ii) loopless multigraph, (iii) simple graph, (iv) cycle-free graph (forest or tree), (v) caterpillar G=(V,E) such that for all k, d(vk)=dk and ∑w∈N(vk)d(w)=fk (d(v) is the degree of v and N(v) is the set of neighbors of v). Here we show that all these decision problems can be solved in polynomial time if Δ≔maxkdk is bounded. The problems are converted into an integer programming feasibility problem in which both the number of variables and the number of inequalities depend only on Δ but not on n. The problem is motivated by NMR spectroscopy of hydrocarbons. The algorithm has been implemented in the ZIMPL language, and its applicability is demonstrated on trees up to n=1000 vertices. The average reconstruction time for trees with 1000 vertices is still less than 40 ms. © 2023 The Author(s)
| Item Type: | Article |
|---|---|
| Additional Information: | University of Ljubljana, Faculty of Computer and Information Science, Večna pot 113, Ljubljana, 1000, Slovenia University of Minnesota, 206 Church St. SE, Minneapolis, MN 55455, United States Rényi Institute, ELKH, Reáltanoda u. 13-15, Budapest, 1053, Hungary SZTAKI, ELKH, Lágymányosi u. 11, Budapest, 1111, Hungary Vassar College, 124 Raymond Avenue, Poughkeepsie, NY 12604, United States Georgia Institute of Technology North Avenue, Atlanta, GA 30332, United States Export Date: 14 February 2023 CODEN: DAMAD Correspondence Address: Miklós, I.; Rényi Institute, Reáltanoda u. 13-15, Hungary; email: miklos.istvan@renyi.hu Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K132696, KH126853, SNN135643 Funding text 1: I.M. was supported by NKFIH, Hungary grants KH126853 , K132696 and SNN135643 . The project is a continuation of the work done at the 2020 Budapest Semesters in Mathematics. All authors would like to thank the BSM for running the program. Funding text 2: I.M. was supported by NKFIH, Hungary grants KH126853, K132696 and SNN135643. The project is a continuation of the work done at the 2020 Budapest Semesters in Mathematics. All authors would like to thank the BSM for running the program. |
| Uncontrolled Keywords: | NMR-SPECTROSCOPY; NMR spectroscopy; Nuclear magnetic resonance spectroscopy; Integer programming; Polynomial approximation; Degree constraints; Directed graphs; Positive integers; decision problems; Degree sequences; Multigraphs; Bounded degree graphs; Simple++; Loopless; Neighbor degree constraint; Neighbor degree constraint; Degree-sequence; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 30 Mar 2024 20:57 |
| Last Modified: | 30 Mar 2024 20:57 |
| URI: | https://real.mtak.hu/id/eprint/191307 |
Actions (login required)
 |
Edit Item |
