48 papers
Dit artikel biedt een beknopt en zelfstandig bewijs van Delahan's stelling dat elke eenvoudige graaf met knopen als geïnduceerde subgraaf voorkomt in een Steinhaus-graaf met knopen, door gebruik te maken van het concept van genererende indexverzamelingen voor Steinhaus-driehoeken.
Dit artikel introduceert permutatie-matchpuzzels op roosters, karakteriseert de oplosbaarheid ervan via een acyclische voorwaarde, levert een tellende formule voor oplossingen, biedt een lineaire algoritme voor het repareren van onoplosbare gevallen, en toont aan dat de veralgemening met willekeurige permutaties NP-compleet is.
In dit artikel wordt het WELLDOC-eigenschap voor oneindige woorden onderzocht en wordt een criterium voor deze eigenschap afgeleid voor woorden die gegenereerd worden door morfismen.
Dit artikel biedt een volledige karakterisering van interval nest-digrafo's aan de hand van vertex-lineaire ordeningen met verboden patronen, genaamd nest-ordeningen, waarmee het de bestaande theorie over vertex-ordeningskarakteriseringen voor belangrijke subklassen van intervaldigrafo's voltooit.
Dit artikel presenteert een volledige analyse van een sublineair algoritme dat de gemiddelde graad van een graf met begrensd arboriciteit benadert met een querycomplexiteit van , waardoor de logaritmische verliezen en de complexiteit van de oorspronkelijke beschrijving worden vermeden.
Dit artikel presenteert een versie van de matrix-bomenstelling die determinanten relateert aan sommen van arborescentiegewichten in een gerichte graaf met een extra wortel, waarmee bewijzen voor de matrix-bosstelling worden geleverd en toepassingen voor tijds-evolutie en determinantberekening worden onderzocht.
Dit artikel ontwikkelt kwantitatieve hulpmiddelen voor het bestuderen van willekeurige minimum-spanningbomen (MST) in een grafiek, waarbij de kantengewichten onafhankelijk worden getrokken uit willekeurige verdelingen, in tegenstelling tot de meer onderzochte uniforme verdeling van spanningbomen (UST).
Dit artikel onderzoekt de eigenschappen van het lineaire kleuringgetal en levert verbeterde onder- en bovengrenzen op voor verschillende grafklassen, waarmee een eerder vermoeden over de relatie met de boomdiepte wordt onderzocht.
Dit artikel biedt de theoretische onderbouwing voor het -DRESS-raamwerk, dat door middel van een onvoorwaardelijk bewijs en een conditioneel bewijs aantoont dat het de CFI-paren onderscheidt en minstens zo krachtig is als de -WL-hiërarchie.
Dit artikel onderzoekt de waarschijnlijkheid dat een willekeurige collectie -subsets een matrood vormt, identificeert voorwaarden voor het ontstaan van dergelijke matroïden, en verbetert bestaande schattingen voor het aantal matroïden door een algoritme te gebruiken dat werkt voor rang die langzaam groeit met .
Dit artikel levert een volledig bewijs voor de volledige nim-waarde-structuur van additieve aftrekspellen in het primitief kwadratische regime, door te aantonen dat elke nim-waardeserie ligt op een lineaire verschuiving van de klassieke P-posities die worden beschreven door een gesloten formule met Beatty-achtige uitdrukkingen.
Dit artikel ontwikkelt expliciete en compacte formules voor de M-polynoom van zeven verschillende grafproducten, waardoor een unificerend raamwerk ontstaat voor het analyseren van graad-gebaseerde topologische indices.
Dit artikel introduceert twee kwantitatieve methoden voor het berekenen van gewichtsvector uit onvolledige paarwijze vergelijkingen met referentiewaarden, waarbij de optimaliteit van de geometrische variant en de bestaansvoorwaarden van de rekenkundige variant worden bewezen.
Dit artikel presenteert een vast-parameter-tractabele (FPT) algoritme dat het Gallai-Milgram-theorema uitbreidt door te bepalen of een graaf met minder dan paden kan worden bedekt, en levert bovendien de eerste polynomiale tijd-algoritmen voor het bepalen van Hamiltoniciteit in grafen met een onafhankelijkheidsgetal van maximaal drie.
Dit artikel introduceert en analyseert blok-gescheiden overpartities, een nieuwe combinatorische familie waarbij de overlijning van blokken wordt beperkt tot Fibonacci-achtige patronen, wat leidt tot een Euler-productontbinding, diverse recursieve representaties en een asymptotische groei die overeenkomt met die van gewone partities.
Dit artikel bewijst een verzwakte versie van een conjectuur over bomenontbindingen in grafen die en het rooster als geïnduceerde minor uitsluiten, door te tonen dat dergelijke grafen een bomenontbinding toelaten waarbij de zakken een beperkte onafhankelijkheidsgetal hebben op basis van specifieke afstandsparameters.
Dit artikel introduceert een alomvattende generalisatie van de switch-operatie op -grafieken, bestudeert de daaruit voortvloeiende homomorfismen axiomatisch, lost diverse open problemen op, bewijst het bestaan van een categorisch product en bepaalt het chromatisch getal voor bossen.
Dit artikel onderzoekt de complexiteit van het herschikingsprobleem voor afstand- dominante verzamelingen, waarbij het een interessante dichotomie aantoont door aan te tonen dat het probleem op splitgrafen voor in ligt, terwijl het op andere graafklassen zoals planaire en bipartiete grafen -volledig blijft.
Dit artikel onderzoekt de parameteriseringscomplexiteit van het kortste-padprobleem met positieve disjunctieve constraints en levert kerningresultaten met of vertices voor de oplossingsgrootte , evenals vast-parameter-tractabiliteitsresultaten voor structurele parameters van de dwanggraaf.
Dit artikel onderzoekt de haalbaarheid van het oplossen van de 3D-heterogene Poisson-vergelijking voor fractuurstroming met quantumlineaire-systeemalgoritmen, waarbij wordt aangetoond dat hoewel blokcodering van de voorwaarderingsmatrix de effectieve conditienummer niet verbetert, het quantumalgoritme toch een superieure tijdscomplexiteit en exponentiële geheugenefficiëntie biedt ten opzichte van klassieke methoden.