The even outdegree conjecture for acyclic PLCP-cubes in dimension five

Sonoko Moriyama; Yoshio Okamoto

doi:10.1093/ietisy/e89-d.8.2402

The even outdegree conjecture for acyclic PLCP-cubes in dimension five

Sonoko Moriyama, Yoshio Okamoto

Research output: Contribution to journal › Article › peer-review

Abstract

The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.

Original language	English
Pages (from-to)	2402-2404
Number of pages	3
Journal	IEICE Transactions on Information and Systems
Volume	E89-D
Issue number	8
DOIs	https://doi.org/10.1093/ietisy/e89-d.8.2402
Publication status	Published - 2006 Aug
Externally published	Yes

Keywords

Holt-Klee condition
Linear complementarity problems
Unique sink orientations

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Vision and Pattern Recognition
Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1093/ietisy/e89-d.8.2402

Cite this

@article{7789e431c4b9466c97267189e9f6512e,

title = "The even outdegree conjecture for acyclic PLCP-cubes in dimension five",

abstract = "The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.",

keywords = "Holt-Klee condition, Linear complementarity problems, Unique sink orientations",

author = "Sonoko Moriyama and Yoshio Okamoto",

year = "2006",

month = aug,

doi = "10.1093/ietisy/e89-d.8.2402",

language = "English",

volume = "E89-D",

pages = "2402--2404",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "8",

}

TY - JOUR

T1 - The even outdegree conjecture for acyclic PLCP-cubes in dimension five

AU - Moriyama, Sonoko

AU - Okamoto, Yoshio

PY - 2006/8

Y1 - 2006/8

N2 - The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.

AB - The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.

KW - Holt-Klee condition

KW - Linear complementarity problems

KW - Unique sink orientations

UR - http://www.scopus.com/inward/record.url?scp=33747867468&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747867468&partnerID=8YFLogxK

U2 - 10.1093/ietisy/e89-d.8.2402

DO - 10.1093/ietisy/e89-d.8.2402

M3 - Article

AN - SCOPUS:33747867468

SN - 0916-8532

VL - E89-D

SP - 2402

EP - 2404

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 8

ER -

The even outdegree conjecture for acyclic PLCP-cubes in dimension five

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this